<代码随想录> 算法训练营-2024.12.19
今日专题:动态规划 完全背包(每个物品可以选n次)
动态规划分析的时候把状态转移图画出来
先遍历物品再遍历背包求排列数,先遍历背包再遍历物品求组合数
518. 零钱兑换 II
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
@cache
def dfs(i, j):
if j <= 0:
return 1
if i < 0:
return 0
if coins[i] > j:
return dfs(i - 1, j)
return dfs(i - 1, j) + dfs(i, j - coins[i])
return dfs(len(coins) - 1, amount)
377. 组合总和 Ⅳ
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 怎么处理不同排序是不同的结果呢
# dp[i][j]=dp[i-1][j]+dp[i][j-nums[i]]
size = len(nums)
dp = [[0 for _ in range(target + 1)] for _ in range(size)]
for i in range(size):
dp[i][0] = 1
for n in range(1, target + 1):
for m in range(size):
if n >= nums[m]:
dp[m][n] = dp[m - 1][n] + dp[-1][n - nums[m]]
else:
dp[m][n] = dp[m - 1][n]
return dp[size - 1][target]