> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/70.-climbing-stairs.md).

# 70. Climbing Stairs (1D-dp)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MduX1qD-MRPbuXzM2E8%2F-MduawPz2TNB70v55xJp%2Fimage.png?alt=media\&token=d2834c09-d423-4a41-a140-983fb8cf5ca7)

## DP

time: O(n)

space: O(n)

```java
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        int dp[] = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
```

## use fib

time: O(n)

space: O(1)

```java
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        int first = 1;
        int second = 2;
        
        for (int i = 3; i <= n ; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}
```

why return second? because our goal is to use 2 varibles to rotate the value, so&#x20;

first = second

second = third(outcome)

at last second is the result (third)

ex: n = 3

-> ans. = 3 = 2 + 1

first = second = 2

second = outcome = 3

-> ans = second = 3