0070-爬楼梯 #

https://leetcode.cn/problems/climbing-stairs/submissions/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

思路分析 #

这题一开始会有一种无从下手的感觉，从n级楼梯直接开始，我们会发现前面的爬法会无限复杂。

但是我们倒过来，从第一级台阶开始，如 n = 1, 那么只有一种解法，就是爬一级。 当 n = 2 的时候，会有两种解法，一种是 一次爬一级，另一种是，一次爬两级。

好，当我们到第三级台阶的时候，我们会发现，此时，要么 从第一级台阶，跨两步上来，要么是从第二级台阶，跨1步上来。 所以第三级的解法，就是 F(3) = F(1)(然后跨两阶) + F(2)(然后跨一阶)，同理，到第四级的时候，解法为 F(4) = F(2)(然后跨两阶) + F(3)(然后跨一阶)

写到这里，我们会发现，这个其实就是 斐波那契数列，只不过是斐波那契数列直接开始就告诉了你 F(n) = F(n-1) + F(n-2)，而本题则需要自己推导出来。

其实很多动态规划类的题目，都是用这种方式来解决的，先从最开始的最小范围解决，逐步衍生到后一步，来根据前置结果继续计算。

动态规划：最重要就是确定状态转移方程，本地的状态转移方程就是 F(n) = F(n-1) + F(n-2)，有了状态转移方程，我们代码就可以很快写出来了，注意下面 i 是从3开始循环第三级的，因为 dp[0] = 0 ，这个意义不大，就是第0级，没有走法。

实现代码 #

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

思路：完全背包解法 #

如果爬楼梯的方式是 1-m 种方式，就是完全背包问题。

实现代码 #

public class Solution {
    public int ClimbStairs(int n) {
        //dp表示到达当前台阶需要的步数
        int[] dp = new int[n+1];
        dp[0] = 1;
        int m = 2; //完全背包：m种跳法
        for(int i=1;i<=n;i++){ //遍历背包
            for(int j=1; j<=2; j++){ //遍历物品
                if(i>=j){
                    dp[i]+=dp[i-j];
                }
            }
        }
        return dp[n];
    }
}