70. Climbing Stairs

70. Climbing Stairs

Difficulty: 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?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

1.Brute Force

通过递归遍历所有可能性，方法出入栈的开销大，会超时。

class Solution {
    public int climbStairs(int n) {
        return climbStairs(n, 0);
    }
    
    public int climbStairs(int n, int current) {
        if (current == n) return 1;
        if (current > n) return 0;
        int count = 0;
        count += climbStairs(n, current + 1);
        count += climbStairs(n, current + 2);
        return count;
    }
}

2.DP

记录前两个元素的路径数，最终得到n的路径数

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

可以看出这里其实不需要用数组，只需要前两个元素即可：

class Solution {
    public int climbStairs(int n) {
        int a = 0, b = 1;
        for (int i = 1; i < n; i++) {
            if (i % 2 == 0) {
                b += a;
            } else {
                a += b;
            }
        }
        return a + b;
    }
}

3.斐波那契通项公式

通过公式直接算出，建议自行学习原理