1.完全背包理论基础

思路

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

每件商品都有无限个！

问背包能背的物品最大价值是多少？

01背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序经行分析！

关于01背包我如下两篇已经进行深入分析了：

• 动态规划：关于01背包问题，你该了解这些！(opens new window)
• 动态规划：关于01背包问题，你该了解这些！（滚动数组）

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历

在动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中也做了讲解。

dp状态图如下：

相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。

其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？

这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？

难道就不能遍历背包容量在外层，遍历物品在内层？

看过这两篇的话：

• 动态规划：关于01背包问题，你该了解这些！(opens new window)
• 动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)

就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

遍历物品在外层循环，遍历背包容量在内层循环，状态如图：

遍历背包容量在外层循环，遍历物品在内层循环，状态如图：

看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）。

总结

对于纯完全背包问题，其for循环的先后循环是可以颠倒的！

先遍历物品，再遍历背包

public class Complete_Knapsack_Problem {
    //先遍历物品，再遍历背包
    private static void testCompletePack(){
        int[] weight = {1, 3, 4};//定义了三种物品，它们的重量分别是1、3、4，对应的价值分别是15、20、30。
        int[] value = {15, 20, 30};
        int bagWeight = 4;//背包的总容量是4。
        int[] dp = new int[bagWeight + 1];//dp数组用于存储每个容量下的最大价值。数组的大小是背包容量加1，因为容量从0开始。
        for (int i = 0; i < weight.length; i++){//外层循环遍历所有物品，内层循环遍历所有可能的背包容量。对于每个物品i和每个容量j，我们考虑两种情况：不取当前物品，那么当前容量下的最大价值仍然是dp[j]。取当前物品，那么当前容量下的最大价值是dp[j - weight[i]] + value[i]，即取走当前物品后剩余容量下的最大价值加上当前物品的价值。
            for (int j = weight[i]; j <= bagWeight; j++){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);//比较了这两种情况，取两者的最大值作为当前容量下的最大价值。
            }
        }
        for (int maxValue : dp){//遍历dp数组，输出每个容量下的最大价值。
            System.out.println(maxValue + "   ");
        }
    }
   
}

• 时间复杂度：两种方法的时间复杂度都是 𝑂(𝑛×𝑏𝑎𝑔𝑊𝑒𝑖𝑔ℎ𝑡)O(n×bagWeight)。
• 空间复杂度：两种方法的空间复杂度都是 𝑂(𝑏𝑎𝑔𝑊𝑒𝑖𝑔ℎ𝑡)O(bagWeight)

先遍历背包，再遍历物品

public class Complete_Knapsack_Problem {
    //先遍历背包，再遍历物品
    private static void testCompletePackAnotherWay(){
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 1; i <= bagWeight; i++){//外层循环是遍历所有可能的背包容量，从1开始到背包的最大容量。内层循环遍历所有物品。对于每个容量i和每个物品j，我们检查当前容量是否足够放下这个物品（即i - weight[j] >= 0）。如果足够，我们考虑两种情况：不取当前物品，那么当前容量下的最大价值仍然是dp[i]。取当前物品，那么当前容量下的最大价值是dp[i - weight[j]] + value[j]，即取走当前物品后剩余容量下的最大价值加上当前物品的价值。
            for (int j = 0; j < weight.length; j++){
                if (i - weight[j] >= 0){
                    dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);//较了这两种情况，取两者的最大值作为当前容量下的最大价值。
                }
            }
        }
        for (int maxValue : dp){//遍历dp数组，输出每个容量下的最大价值。
            System.out.println(maxValue + "   ");
        }
    }
}

• 时间复杂度：两种方法的时间复杂度都是 𝑂(𝑛×𝑏𝑎𝑔𝑊𝑒𝑖𝑔ℎ𝑡)O(n×bagWeight)。
• 空间复杂度：两种方法的空间复杂度都是 𝑂(𝑏𝑎𝑔𝑊𝑒𝑖𝑔ℎ𝑡)O(bagWeight)

2.零钱兑换II

力扣题目链接(opens new window)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

• 输入: amount = 5, coins = [1, 2, 5]
• 输出: 4

解释: 有四种方式可以凑成总金额:

• 5=5
• 5=2+2+1
• 5=2+1+1+1
• 5=1+1+1+1+1

示例 2:

• 输入: amount = 3, coins = [2]
• 输出: 0
• 解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

• 输入: amount = 10, coins = [10]
• 输出: 1

注意，你可以假设：

• 0 <= amount (总金额) <= 5000
• 1 <= coin (硬币面额) <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

思路

这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。

对完全背包还不了解的同学，可以看这篇：动态规划：关于完全背包，你该了解这些！(opens new window)

但本题和纯完全背包不一样，纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数！

注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？

例如示例一：

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合，都是 2 2 1。

如果问的是排列数，那么上面就是两种排列了。

组合不强调元素之间的顺序，排列强调元素之间的顺序。 其实这一点我们在讲解回溯算法专题的时候就讲过了哈。

动规五步曲来分析如下：

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

dp[j]：凑成总金额j的货币组合数为dp[j]

1. 确定递推公式

dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。

所以递推公式：dp[j] += dp[j - coins[i]];

这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇494. 目标和 (opens new window)中就讲解了，求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];

1. dp数组如何初始化

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

那么 dp[0] = 1 有没有含义，其实既可以说 凑成总金额0的货币组合数为1，也可以说 凑成总金额0的货币组合数为0，好像都没有毛病。

但题目描述中，也没明确说 amount = 0 的情况，结果应该是多少。

这里我认为题目描述还是要说明一下，因为后台测试数据是默认，amount = 0 的情况，组合数为1的。

下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

dp[0]=1还说明了一种情况：如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选法。

1. 确定遍历顺序

本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？

我在动态规划：关于完全背包，你该了解这些！ (opens new window)中讲解了完全背包的两个for循环的先后顺序都是可以的。

但本题就不行了！

因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

而本题要求凑成总和的组合数，元素之间明确要求没有顺序。

所以纯完全背包是能凑成总和就行，不用管怎么凑的。

本题是求凑出来的方案个数，且每个方案个数是为组合数。

那么本题，两个for循环的先后顺序可就有说法了。

我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

这种遍历顺序中dp[j]里计算的是组合数！

如果把两个for交换顺序

此时dp[j]里算出来的就是排列数！

可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）

1. 举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：

最后红色框dp[amount]为最终结果。

总结

本题的递推公式，其实我们在494. 目标和 (opens new window)中就已经讲过了，而难点在于遍历顺序！

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

public class Change_Making_ProblemII {
    public int change1(int amount, int[] coins) {//接受两个参数：amount表示需要兑换的总金额，coins是一个数组，包含了可用的硬币面额。
        int[] dp = new int[amount + 1];//dp数组用于存储到达每个金额的不同组合数。数组的大小是amount + 1，因为金额从0开始。dp[0]被初始化为1，表示有1种方式可以组成金额0（即不使用任何硬币）。
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {//外层循环遍历所有硬币面额，内层循环遍历从当前硬币面额到总金额的所有可能金额。对于每个硬币面额coins[i]和每个金额j，我们更新dp[j]的值，增加dp[j - coins[i]]的值。这是因为如果我们已经有了组成j - coins[i]金额的方法，那么我们可以通过添加一个coins[i]面额的硬币来组成j金额。
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];//dp[j]的值是组成j金额的方法数和组成j - coins[i]金额的方法数之和。
            }
        }
        return dp[amount];//返回dp[amount]的值，即组成总金额amount的不同组合数。
    }
  
    }

• 时间复杂度：O(amount * coins.length)
• 空间复杂度：O(amount)

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

public class Change_Making_ProblemII {
    public int change2(int amount, int[] coins) {//接受两个参数：amount表示需要兑换的总金额，coins是一个数组，包含了可用的硬币面额。
        int[][] dp = new int[coins.length][amount+1];//dp[i][j]表示使用前i种硬币组成金额j的不同组合数。数组的大小是coins.length乘以amount+1。初始化时，对于所有的硬币组合，组成金额0的组合数为1（即不使用任何硬币），所以dp[i][0]被初始化为1。
        for(int i = 0; i < coins.length; i++){
            dp[i][0] = 1;
        }
        for(int j = coins[0]; j <= amount; j++){//处理第一个硬币的特殊情况。由于第一个硬币可以无限使用，我们可以直接将dp[0][j]的值更新为dp[0][j-coins[0]]的值，这样就可以累加使用一个或多个第一个硬币面额的硬币组成金额j的组合数。
            dp[0][j] += dp[0][j-coins[0]];
        }
        for(int i = 1; i < coins.length; i++){//外层循环遍历所有硬币面额（从第二个硬币开始），内层循环遍历从1到总金额的所有可能金额。对于每个硬币面额i和每个金额j，我们考虑两种情况：如果j小于当前硬币面额coins[i]，则不能使用这个硬币，所以dp[i][j]的值与dp[i-1][j]相同。如果j大于或等于当前硬币面额coins[i]，则有两种选择：不使用当前硬币，dp[i][j]的值与dp[i-1][j]相同；或者使用至少一个当前硬币，dp[i][j]的值是dp[i][j-coins[i]]（使用一个当前硬币）和dp[i-1][j]（不使用当前硬币）的和。
            for(int j = 1; j <= amount; j++){
                if(j < coins[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j];
            }
        }
        return dp[coins.length-1][amount];//函数返回dp[coins.length-1][amount]的值，即使用所有硬币组成总金额amount的不同组合数。
    }

    }

• 时间复杂度：O(amount * coins.length)

• 空间复杂度：O(coins.length * amount)

3.本周小结动态规划

周一

动态规划：目标和！ (opens new window)要求在数列之间加入+ 或者 -，使其和为S。

所有数的总和为sum，假设加法的总和为x，那么可以推出x = (S + sum) / 2。

S 和 sum都是固定的，那此时问题就转化为01背包问题（数列中的数只能使用一次）: 给你一些物品（数字），装满背包（就是x）有几种方法。

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

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

1. 确定递推公式

dp[j] += dp[j - nums[i]]

注意：求装满背包有几种方法类似的题目，递推公式基本都是这样的。

1. dp数组如何初始化

dp[0] 初始化为1 ，dp[j]其他下标对应的数值应该初始化为0。

1. 确定遍历顺序

01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。

1. 举例推导dp数组

输入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下：

周二

这道题目动态规划：一和零！ (opens new window)算有点难度。

不少同学都以为是多重背包，其实这是一道标准的01背包。

这不过这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。

所以这是一个二维01背包！

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

1. 确定递推公式

dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

字符串集合中的一个字符串0的数量为zeroNum，1的数量为oneNum。

1. dp数组如何初始化

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

1. 确定遍历顺序

01背包一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

1. 举例推导dp数组

以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例

最后dp数组的状态如下所示：

周三

此时01背包我们就讲完了，正式开始完全背包。

在动态规划：关于完全背包，你该了解这些！ (opens new window)中我们讲解了完全背包的理论基础。

其实完全背包和01背包区别就是完全背包的物品是无限数量。

递推公式也是一样的，但难点在于遍历顺序上！

完全背包的物品是可以添加多次的，所以遍历背包容量要从小到大去遍历

那么为什么要先遍历物品，在遍历背包呢？ （灵魂拷问）

其实对于纯完全背包，先遍历物品，再遍历背包 与 先遍历背包，再遍历物品都是可以的。我在文中动态规划：关于完全背包，你该了解这些！ (opens new window)也给出了详细的解释。

这个细节是很多同学忽略掉的点，其实也不算细节了，相信不少同学在写背包的时候，两层for循环的先后循序搞不清楚，靠感觉来的。

所以理解究竟是先遍历啥，后遍历啥非常重要，这也体现出遍历顺序的重要性！

在文中，我也强调了是对纯完全背包，两个for循环先后循序无所谓，那么题目稍有变化，可就有所谓了。

周四

在动态规划：给你一些零钱，你要怎么凑？ (opens new window)中就是给你一堆零钱（零钱个数无限），为凑成amount的组合数有几种。

注意这里组合数和排列数的区别！

看到无限零钱个数就知道是完全背包，

但本题不是纯完全背包了（求是否能装满背包），而是求装满背包有几种方法。

这里在遍历顺序上可就有说法了。

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

总结

介绍关于动态规划，你该了解这些！ (opens new window)中就强调了 递推公式仅仅是 动规五部曲里的一小部分， dp数组的定义、初始化、遍历顺序，哪一点没有搞透的话，即使知道递推公式，遇到稍稍难一点的动规题目立刻会感觉写不出来了。

4.组合总和 Ⅳ

力扣题目链接(opens new window)

难度：中等

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

思路

对完全背包还不了解的同学，可以看这篇：动态规划：关于完全背包，你该了解这些！(opens new window)

本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！

弄清什么是组合，什么是排列很重要。

组合不强调顺序，(1,5)和(5,1)是同一个组合。

排列强调顺序，(1,5)和(5,1)是两个不同的排列。

大家在公众号里学习回溯算法专题的时候，一定做过这两道题目回溯算法：39.组合总和 (opens new window)和回溯算法：40.组合总和II (opens new window)会感觉这两题和本题很像！

但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。

如果本题要把排列都列出来的话，只能使用回溯算法爆搜。

动规五部曲分析如下：

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

dp[i]: 凑成目标正整数为i的排列个数为dp[i]

1. 确定递推公式

dp[i]（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来。

因为只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp[i]的一部分。

在动态规划：494.目标和 (opens new window)和 动态规划：518.零钱兑换II (opens new window)中我们已经讲过了，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];

本题也一样。

1. dp数组如何初始化

因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。

至于dp[0] = 1 有没有意义呢？

其实没有意义，所以我也不去强行解释它的意义了，因为题目中也说了：给定目标值是正整数！ 所以dp[0] = 1是没有意义的，仅仅是为了推导递推公式。

至于非0下标的dp[i]应该初始为多少呢？

初始化为0，这样才不会影响dp[i]累加所有的dp[i - nums[j]]。

1. 确定遍历顺序

个数可以不限使用，说明这是一个完全背包。

得到的集合是排列，说明需要考虑元素之间的顺序。

本题要求的是排列，那么这个for循环嵌套的顺序可以有说法了。

在动态规划：518.零钱兑换II (opens new window)中就已经讲过了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！

所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

1. 举例来推导dp数组

我们再来用示例中的例子推导一下：

如果代码运行处的结果不是想要的结果，就把dp[i]都打出来，看看和我们推导的一不一样。

总结

求装满背包有几种方法，递归公式都是一样的，没有什么差别，但关键在于遍历顺序！

本题与动态规划：518.零钱兑换II (opens new window)就是一个鲜明的对比，一个是求排列，一个是求组合，遍历顺序完全不同。

public class Combination_SumIV {
    public int combinationSum4(int[] nums, int target) {//nums是一个整数数组，包含了候选数字，target是需要达到的目标数字。
        int[] dp = new int[target + 1];//dp数组用于存储达到每个金额的不同组合数。数组的大小是target + 1，因为金额从0开始。dp[0]被初始化为1，表示有1种方式可以组成金额0（即不使用任何数字）。
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {//外层循环遍历从0到target的所有可能金额，内层循环遍历所有候选数字。对于每个金额i和每个候选数字nums[j]，如果i大于等于nums[j]，则可以考虑使用这个数字来组成金额i。具体来说，如果使用数字nums[j]来组成金额i，那么组成金额i的组合数就是组成金额i - nums[j]的组合数加到dp[i]上。这是因为每个dp[i - nums[j]]代表了一个有效的组合，我们只需将nums[j]添加到这些组合中即可形成新的组合。
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];//返回dp[target]的值，即所有加和等于目标数target的组合数量。
    }
}

• 时间复杂度为O(target * nums.length)。
• 空间复杂度为O(target)。

5.爬楼梯（进阶版）

卡码网：57. 爬楼梯(opens new window)

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

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

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

输入描述：输入共一行，包含两个正整数，分别表示n, m

输出描述：输出一个整数，表示爬到楼顶的方法数。

输入示例：3 2

输出示例：3

提示：

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

• 1 阶 + 1 阶 + 1 阶段
• 1 阶 + 2 阶
• 2 阶 + 1 阶

思路

之前讲这道题目的时候，因为还没有讲背包问题，所以就只是讲了一下爬楼梯最直接的动规方法（斐波那契）。

这次终于讲到了背包问题，我选择带录友们再爬一次楼梯！

这道题目 我们在动态规划：爬楼梯 (opens new window)中已经讲过一次了，这次我又给本题加点料，力扣上没有原题，所以可以在卡码网57. 爬楼梯 (opens new window)上来刷这道题目。

我们之前做的 爬楼梯 是只能至多爬两个台阶。

这次改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？

这又有难度了，这其实是一个完全背包问题。

1阶，2阶，.... m阶就是物品，楼顶就是背包。

每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了！

和昨天的题目动态规划：377. 组合总和 Ⅳ (opens new window)基本就是一道题了。

动规五部曲分析如下：

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

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

1. 确定递推公式

在动态规划：494.目标和 (opens new window)、 动态规划：518.零钱兑换II (opens new window)、动态规划：377. 组合总和 Ⅳ (opens new window)中我们都讲过了，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];

本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]

那么递推公式为：dp[i] += dp[i - j]

1. 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这样才不会影响结果

1. 确定遍历顺序

这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！

所以需将target放在外循环，将nums放在内循环。

每一步可以走多次，这是完全背包，内循环需要从前向后遍历。

1. 举例来推导dp数组

介于本题和动态规划：377. 组合总和 Ⅳ (opens new window)几乎是一样的，这里我就不再重复举例了。

总结

如果我来面试的话，我就会先给候选人出一个 本题原题，看其表现，如果顺利写出来，进而在要求每次可以爬[1 - m]个台阶应该怎么写。

顺便再考察一下两个for循环的嵌套顺序，为什么target放外面，nums放里面。

这就能考察对背包问题本质的掌握程度，候选人是不是刷题背公式，一眼就看出来了。

public class Climbing_Stairs_Advanced {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);//从标准输入流（键盘）读取数据。
        int m, n;//两个整型变量m和n，分别用于存储硬币的面额种类和需要凑成的金额。
        while (sc.hasNextInt()) {//使用while循环来不断地从输入中读取数据，直到没有更多的整数输入。hasNextInt()方法用于检查输入中是否还有下一个整数。
            n = sc.nextInt();//读取下一个整数并赋值给变量n。
            m = sc.nextInt();//读取下一个整数并赋值给变量m。
            int[] dp = new int[n + 1];//声明并初始化一个长度为n+1的数组dp，用于存储动态规划的中间结果。数组的索引从0到n，因此长度需要是n+1。
            dp[0] = 1;//初始化dp[0]为1，表示凑成金额0有一种方式，即不使用任何硬币。
            for (int j = 1; j <= n; j++) {//外层循环，遍历从1到n的所有金额。
                for (int i = 1; i <= m; i++) {//内层循环，遍历从1到m的所有硬币面额。
                    if (j - i >= 0) dp[j] += dp[j - i];//如果当前金额j减去硬币面额i的结果非负，说明可以使用面额为i的硬币来凑成金额j。因此，将dp[j-i]的值加到dp[j]上，表示凑成金额j的组合数增加了dp[j-i]种。
                }
            }
            System.out.println(dp[n]);//输出最终结果，即dp[n]，表示凑成金额n的不同硬币组合的数量。
        }
    }
}

• 时间复杂度：O(n * m)
• 空间复杂度：O(n)