518. 零钱兑换 II -- 完全背包

518. 零钱兑换 II

这道题其实就是一个完全背包问题，关于背包问题的相关文章见：

1. 01背包问题 – 动态规划
2. 完全背包问题

class CoinChange:"""完全背包518. 零钱兑换 IIhttps://leetcode.cn/problems/coin-change-ii/"""def solution(self, amount: int, coins: List[int]) -> int:n = len(coins)#  dp[i][j]: 若只使⽤前 i 个物品（可以重复使⽤），当背包容量为 j 时，有 dp[i][j] 种⽅法可以装满背包。dp = [[0 for _ in range(amount+1)] for _ in range(n+1)]# base casefor i in range(n + 1):dp[i][0] = 1for i in range(1, n+1):for j in range(1, amount+1):if j - coins[i-1] >= 0:dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]else:dp[i][j] = dp[i - 1][j]return dp[n][amount]def solution2(self, amount: int, coins: List[int]) -> int:"""空间压缩，二维变一维:param amount::param coins::return:"""n = len(coins)#  dp[j]: 当背包容量为 j 时，有 dp[j] 种⽅法可以装满背包。dp = [0 for _ in range(amount + 1)]# base casedp[0] = 1for i in range(n):# 这里只能从前往后正向遍历，因为要考虑重复使用的情况，区别在于这里 dp[i][j-coins[i-1]]# 当使用了coins[i]这枚硬币时，可重复多次使用，所以不是 dp[i-1][j-coins[i-1]]# dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]for j in range(1, amount + 1):if j - coins[i] >= 0:dp[j] = dp[j] + dp[j - coins[i]]return dp[amount]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！