难度: Medium
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10] 输出：1
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins 中的所有值 互不相同0 <= amount <= 5000运行时间: 58 ms
内存: 16.2 MB
class Solution:
def change(self, amount:int, coins:List[int]) -> int:
if amount == 0:
return 1
coins.sort(reverse=True)
dp = [0] * (amount + 1)
for c in coins:
if c > amount:
continue
dp[c] += 1
for i in range(c, amount - c + 1):
dp[i + c] += dp[i]
return dp[-1]
这是一道典型的动态规划问题。我们定义一个一维数组 dp，其中 dp[i] 表示组成金额 i 的硬币组合数。初始状态下，除了 dp[0] 为 1（表示金额为 0 的组合数为 1）外，其余都为 0。我们遍历每一种硬币，对于每个硬币 c，我们从 c 开始更新 dp 数组，即对于每个大于等于 c 的 i，更新 dp[i] += dp[i - c]。这样做的意义在于，对于当前的硬币 c，它可以与组成金额 i - c 的所有组合组合在一起，形成金额 i 的组合。
时间复杂度: O(n * amount)
空间复杂度: O(amount)
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
if amount == 0:
return 1
coins.sort(reverse=True)
dp = [0] * (amount + 1)
dp[0] = 1 # 初始化dp[0]为1，表示金额为0的组合数为1
for c in coins:
for i in range(c, amount + 1):
dp[i] += dp[i - c]
return dp[-1]
在动态规划中，dp[0] 被初始化为 1 是为了表示组成金额 0 的方法恰好有一种，即不使用任何硬币。这是一个基本的边界条件，允许我们在计算较大金额时，累加不同硬币带来的组合数。如果将 dp[0] 初始化为 0 或其他值，将无法正确地体现出使用 0 枚硬币来组成金额 0 的情况，这将导致最终的动态规划解决方案无法正确地计数所有可能的组合方式。
硬币数组的逆序排序对最终的组合总数结果没有影响，因为总数只与硬币种类和数量有关，而不依赖于硬币处理的顺序。然而，从硬币值大到小的顺序可能会对算法的空间局部性有轻微的影响，理论上可能对缓存效率有一定的影响，但这种影响通常很小，不会显著改变算法的总体时间复杂度。不过，就算法的正确性而言，硬币的顺序无关紧要。
从金额 c 开始更新 dp 数组而不是从 0 开始的主要原因是效率。金额小于 c 的情况下，使用硬币 c 是不可能的，因此 dp[i] 不会被硬币 c 影响，不需更新。从 c 开始可以避免不必要的计算，减少循环次数，提高算法的效率。此外，这种方法确保只有在硬币 c 可以被使用时，我们才考虑将其加入到组合中，从而正确地更新 dp 数组。
如果 coins 数组中包含重复值，对于最终的输出结果并没有影响，因为算法计算的是所有可能的组合方式，重复的硬币也视为独立的硬币处理。从性能的角度来看，重复值可能会导致一些重复的计算，从而略微增加计算时间，但这种影响通常不会很大。最终的时间复杂度仍然主要依赖于硬币种类数和金额大小。