代码随想录算法训练营Day37

完全背包
力扣517.零钱兑换【medium】
力扣518.零钱兑换【medium】
力扣377.组合总和Ⅳ【meidum】

一、完全背包

• 有 n 种物品，可以重复使用
• 在转为一维数组时：一般是先物品后背包，物品是正序的，背包也是正序
• 在只用一个一维数组的情况下，要注意转移来源
  • 1. 不能被覆盖
  • 2. 必须已经计算出来。
• 按照这个要求，正序遍历会导致 0-1 背包状态被覆盖，而完全背包则是正确的（转移来源被计算出来，且不存在被覆盖的问题）；逆序遍历对于 0-1 背包是正确的（转移来源是上一行的，早就被计算出来了且没有被覆盖），而完全背包则不行（转移来源没有被计算出来）。
• 01背包 在转为i一维数组：背包是逆序的，因为如果是正序，会出现重复计数，转移来源是上一行的
• 完全背包 则需要叠加左边的状态

---

二、力扣322.零钱兑换【medium】

题目链接：力扣322.零钱兑换

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• $f[i][c]$表示在$coins[0]$ 到 $coins[i]$ 中选出最少的硬币个数凑出金额 $c$

2、代码

记忆化搜索

• 时间复杂度：$O(n\ast amount)$
• 空间复杂度：$O(n\ast amount)$

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)@cachedef dfs(i:int, c:int) -> int:if i < 0:return 0 if c == 0 else infif c < coins[i]:return dfs(i - 1, c)return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)ans = dfs(n - 1, amount)return ans if ans < inf else -1

翻译递推：动态规划-二维数组

• 时间复杂度：$O(n\ast amount)$
• 空间复杂度：$O(n\ast amount)$

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)f = [[inf] * (amount + 1) for _ in range(n + 1)]f[0][0] = 0for i, x in enumerate(coins):for c in range(amount + 1):if c < x:f[i + 1][c] = f[i][c]else:f[i + 1][c] = min(f[i][c], f[i + 1][c - x] + 1)ans = f[n][amount]return ans if ans < inf else -1

空间优化：动态规划 - 一维数组

• 时间复杂度：$O(n\ast amount)$
• 空间复杂度：$O(amount)$

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)f = [0] + [inf] * (amount)for x in coins:for c in range(x, amount + 1):f[c] = min(f[c], f[c - x] + 1)ans = f[amount]return ans if ans < inf else -1

---

三、力扣518.零钱兑换【medium】

题目链接：力扣518.零钱兑换

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 与上题一致，这边问的是方法数
• 所以这边要小心状态方程 和 初值的设置！
• $f[i][c]$表示在$coins[0]$ 到 $coins[i]$ 中选出硬币个数可以凑出金额 $c$ 的方法数！

2、代码

记忆化搜索

• 时间复杂度：$O(n\ast amount)$
• 空间复杂度：$O(n\ast amount)$

class Solution:def change(self, amount: int, coins: List[int]) -> int:n = len(coins)@cachedef dfs(i:int, c:int) -> int:if i < 0:return 1 if c == 0 else 0if c < coins[i]:return dfs(i - 1,c)return dfs(i - 1, c) + dfs(i, c - coins[i]) return dfs(n - 1, amount)

翻译递推：动态规划-二维数组

• 时间复杂度：$O(n\ast amount)$
• 空间复杂度：$O(n\ast amount)$

class Solution:def change(self, amount: int, coins: List[int]) -> int:n = len(coins)f = [[0] * (amount + 1) for _ in range( n + 1)]f[0][0] = 1for i, x in enumerate(coins):for c in range(amount + 1):if c < x:f[i + 1][c] = f[i][c]else:f[i + 1][c] = f[i][c] + f[i + 1][c - x]return f[n][amount]

空间优化：动态规划 - 一维数组

• 时间复杂度：$O(n\ast amount)$
• 空间复杂度：$O(amount)$

class Solution:def change(self, amount: int, coins: List[int]) -> int:n = len(coins)f = [1] + [0] * (amount)for x in coins:for c in range(x, amount + 1):f[c] = f[c] + f[c -x]return f[amount]

---

四、力扣377.组合总和Ⅳ【meidum】

题目链接：力扣377.组合总和Ⅳ

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 这道题请注意用例！

• 是排列，不是组合！

• 排列的遍历顺序：先背包再物品

• 组合的遍历顺序：先物品再背包

• 回溯——本质上是爬楼梯：最后一爬有 n = len(nums) 种选择， 所以：

  $dfs(i)=sum(dfs(i-x)forxinnumsifx<=i)$

• 时间复杂度：$O(n\ast target)$

• 空间复杂度：$O(n\ast target)$；优化后：$O(target)$

2、代码

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:@cachedef dfs(i:int):if i == 0: # 爬完了return 1 return sum (dfs(i - x) for x in nums if x <= i) # 枚举所有可以爬的台阶数return dfs(target)

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:f = [1] + [0] * targetfor i in range(target + 1):for x in nums:if x <= i:f[i] += f[i - x]return f[target]

---