代码随想录算法训练营第四十四天|70. 爬楼梯（进阶版）

70. 爬楼梯（进阶版）

多重背包问题，代取商品就是从1：m的数组，背包的容量就是n，由于是求方法数，所以递推公式为

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

因为是排序问题，所以需要先循环容量，后循环商品

322. 零钱兑换

此题是求最小的情况，也就是把背包装满所用的最小的商品数，

初始化中除了dp[0]是正常初始化，其他的dp[i]值都采用INT_MAX进行初始化

因为无论排列和组合，求出的最小商品数都是相同的，所以可以先循环容量，再循环商品，反过来也行。
循环的递推公式为:

if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

首先我们需要求最小值，和求最大值的情况差不多，只是把max换成了min

dp[j - coins[i]] != INT_MAX这个条件是确保在利用dp[j - coins[i]]得到dp[j]的过程中，所使用的一定是更新过的dp[j - coins[i]]，防止dp[j - coins[i]]为未更新过的初始值，影响dp[j]的正常推导。

279.完全平方数

与上题相同，商品数组是由平方项构成的。