> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/zou-ge/climbing_stairs.md).

# Climbing Stairs

<https://leetcode.com/problems/climbing-stairs/description/>

**Easy** You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

## Thoughts

问有多少种想到DP. 和上题类似，到达i阶分别有从i - 1和i - 2两种方法， 因此设f(i)为在i阶的方法数，递推式f\[i] = f\[i - 1] + f\[i - 2], 也就是斐波那契数列。

给定N,

设Fi为从0处往上爬一步或两步到i处的unique path的数目. 求F(N).

## Code

```
class Solution {
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        int[] f = new int[n];
        f[0] = 1;
        f[1] = 2;

        for (int i = 2; i < n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f[n - 1];
    }
}
```

## Analysis

做题耗时: 4min

时间复杂度为O(n), 空间复杂度也是O(n). 但我们观察到f\[i]实际上只有i-1和i-2有关，完全不需要存整个数组。

## Ver.2

```
class Solution {
    public int climbStairs(int n) {
        int[] f = new int[2];
        f[0] = 2; f[1] = 1;

        for (int i = 3; i <= n; i++) {
            f[i % 2] = f[(i - 1) % 2] + f[(i - 2) % 2];
        }
        return f[n % 2];
    }
}
```

## Analysis

TC: O(n), SC: O(1)