题目描述

解题思路

普通思路

• 确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

• 确定递推公式

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

• dp数组如何初始化

不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

• 确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

• 举例推导dp数组

public int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    // dp[i]表示爬到i楼层需要的的方法为dp[i]
    int[] dp = new int[3];
    dp[1] = 1;  // 由于没有楼层0，所有0不做初始化
    dp[2] = 2;
    int sum = 0;
    for (int i = 3; i <= n; i++) {  // 注意从3开始，且要到达n层
        sum = dp[1] + dp[2];
        dp[1] = dp[2];
        dp[2] = sum;
    }
    return dp[2];
}

优化

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

完全背包思路

1阶，2阶，…. m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
重量也就是表示能够跳多少层。

• 确定dp数组以及下标的含义

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。

• 递推公式

求有多少种方法基本上都是dp[i] += dp[i - j]这个递推公式。

• dp数组如何初始化

既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果

• 确认遍历顺序

注意是排列问题，也就是3阶梯可以是[1,2]和[2,1]。所以是先遍历背包，在遍历物品。

• 举例推到DP数组

  // 按照完全背包的思路
  public int climbStairs(int n) {
    // dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
    int[] dp = new int[n + 1];
    int[] weight = {1, 2};
    dp[0] = 1;
    // 先遍历背包,就是总阶梯
    for (int j = 1; j <= n; j++) {
        // 再遍历物品，就是第i个阶梯
        for (int i = 0; i < weight.length; i++) {
            if (j >= weight[i]) {
                dp[j] += dp[j - weight[i]];
            }
        }
    }
    return dp[n];
  }