leetcode刷题-动态规划05

代码随想录动态规划part05|完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯 （进阶） 完全背包理论基础518. 零钱兑换 II【组合问题】377. 组合总和 Ⅳ【排列问题】70. 爬楼梯 （进阶，拓展面试题）【排列问题】

完全背包理论基础

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

0-1背包：

for(i=0; i<weight.size; i++){ //物品 for(j=bagweight; j>=weight[i]; j--) //背包，倒序遍历确保物品只使用一次 dp[j] = max(dp[j], dp[j-weight[i]]+value[i]); }

完全背包：

for(i=0; i<weight.size; i++){ //物品 for(j=weight[i]; j>=bagweight; j++) //背包 dp[j] = max(dp[j], dp[j-weight[i]]+value[i]); }

背包正序遍历，并且物品和背包可以颠倒顺序 先遍历物品再遍历背包：行去更新 先遍历背包再遍历物品：列去更新

518. 零钱兑换 II【组合问题】

leetcode题目链接 代码随想录文档讲解

思路：

这里的amount相当于是背包容量，coins相当于是物品集合；与494目标和有点像（但只能使用一次->0-1背包，但本题可以使用无限次->完全背包），给我们一个集合，装满集合有多少种方法。

dp[j]数组的含义：装满容量为j的背包有dp[j]种方法，最终求dp[amount]dp[j] += dp[i-coins[i]] （与目标和一样）（就是dp[j]=dp[j]+dp[j-coins[i]]放与不放求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]]（一维dp数组））;初始化，dp[0]=1（为了符合递推公式），非零下标初始化为0遍历顺序，本题是完全背包的变体，是考虑组合数，不需要考虑顺序，先遍历背包再遍历物品的话，对于不同的顺序会考虑两次存在重复的答案

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

代码如下：

for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量 dp[j] += dp[j - coins[i]]; } }

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

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

如果把两个for交换顺序，代码如下：

for (int j = 0; j <= amount; j++) { // 遍历背包容量 for (int i = 0; i < coins.size(); i++) { // 遍历物品 if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]]; } }

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

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

python代码：

class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0]*(amount+1) dp[0] = 1 for i in range(len(coins)): for j in range(coins[i], amount+1): dp[j] = dp[j] + dp[j-coins[i]] return dp[amount] 377. 组合总和 Ⅳ【排列问题】

leetcode题目链接 代码随想录文档讲解

思路：

相比上题，本题需要考虑答案的顺序（集合里面考虑元素的排列顺序），排列问题，在遍历顺序上需要先遍历背包，再遍历物品

python代码：

class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0]*(target+1) dp[0] = 1 for j in range(1,target+1): for i in range(len(nums)): if j-nums[i] >= 0: dp[j] += dp[j-nums[i]] return dp[target] 70. 爬楼梯 （进阶，拓展面试题）【排列问题】

卡码网 代码随想录文档讲解

思路：

也是一个考虑排列顺序的完全背包问题，代码中m表示最多可以爬m个台阶，代码中把m改成2就是 力扣：70.爬楼梯的解题思路。 先遍历背包，再遍历物品

def climbing_stairs(n,m): dp = [0]*(n+1) # 背包总容量 dp[0] = 1 # 排列题，注意循环顺序，背包在外物品在内 for j in range(1,n+1): for i in range(1,m+1): if j>=i: dp[j] += dp[j-i] # 这里i就是重量而非index return dp[n] if __name__ == '__main__': n,m = list(map(int,input().split(' '))) print(climbing_stairs(n,m))