70. Climbing Stairs

Question:

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

Thinking:

• Method:
  • 最经典的递归问题。
  • 使用动态规划通过空间换取时间。

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        return backtrace(n - 1, dp) + backtrace(n - 2, dp);
    }
    private static int backtrace(int n, int[] dp){
        if(n < 0) return 0;
        else if(dp[n] != 0)
            return dp[n];
        else{
            dp[n] = backtrace(n - 1, dp) + backtrace(n - 2, dp);
            return dp[n];
        }
    }
}

• Method:
  • 只使用动态规划。
  • dp[n] = dp[n - 1] + dp[n - 2];

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

二刷

这道题还是比较经典的，重新分析这道题，在初始化的阶段我们只对dp[0],dp[1]初始化，而在以后的每个结果中，当前的值是由dp[i - 1]和dp[i -2]构成的，这针对了题目中，只能跨一步或者两步的设定。 ```Java class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= n; i++){ dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }