1.爬楼梯

• 2.17
  • 秒了

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

• 2.4
  • 处理 n= =1 的情况，因为要向前初始化一步
  • 第二次我写的是逻辑后退一步的，第一个版本是符合直觉版本的，忽略 n=0 的情况，因为题目写了不为 0

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

• 12.1
  • 处理边界

状态转移公式就是 “当前状态” 是如何由 “之前状态” 推导出来的数学（或逻辑）关系。 $f(n) = f(n-1) + f(n-2)$

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