python-leetcode-零钱兑换 II
518. 零钱兑换 II - 力扣（LeetCode）
这个问题是 完全背包问题 的一个变体，可以使用 动态规划 来解决。我们定义 dp[i] 为凑成金额 i 的硬币组合数。
思路：
-
定义 DP 数组
设dp[i]表示凑成金额i的组合数，初始化dp[0] = 1（金额为 0 时只有一种方式，即不选取任何硬币）。 -
状态转移方程
dp[j]+=dp[j−coin]dp[j] += dp[j - coin]dp[j]+=dp[j−coin]
对于每个硬币coin，遍历dp[j]（从coin到amount），更新dp[j]：这表示我们可以用
coin这个硬币来扩展dp[j - coin]形成的新组合。 -
遍历顺序
- 外层遍历硬币（确保组合的唯一性）
- 内层遍历金额（从
coin到amount） - 这样保证了组合是无序的，不会重复计算顺序不同但硬币相同的组合。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1 # 凑出金额 0 只有一种方式，即什么都不选
for coin in coins: # 遍历每种硬币
for j in range(coin, amount + 1): # 遍历金额
dp[j] += dp[j - coin] # 累加组合数
return dp[amount]
复杂度分析
- 时间复杂度：O(n × m)，其中
n是amount，m是coins的数量。 - 空间复杂度：O(n)，只使用了一维
dp数组。
总结
这个问题可以通过 动态规划 解决，核心思想是：
dp[j] += dp[j - coin]这一公式表示用coin形成新组合。- 遍历硬币优先，确保组合的唯一性。
- 空间优化：只使用一维数组
dp。