LeetCode 322. Coin Change 题解

LeetCode 322. Coin Change 题解题目描述给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。你可以认为每种硬币的数量是无限的。示例 1输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1示例 2输入coins [2], amount 3 输出-1示例 3输入coins [1], amount 0 输出0解题思路方法动态规划思路定义dp[i]为凑成金额i所需的最少硬币个数状态转移方程dp[i] min(dp[i], dp[i - coin] 1)其中coin是硬币的面额初始化dp[0] 0表示凑成金额 0 不需要硬币其他dp[i]初始化为amount 1表示无法凑成遍历金额从 1 到amount对于每个金额遍历每种硬币面额更新dp[i]复杂度分析时间复杂度O(amount × n)其中 amount 是总金额n 是硬币的种类数。需要遍历 amount 个金额每个金额需要遍历 n 种硬币。空间复杂度O(amount)需要一个长度为 amount 1 的数组来存储状态。代码实现方法动态规划class Solution: def coinChange(self, coins: List[int], amount: int) - int: # 初始化 dp 数组dp[i] 表示凑成金额 i 所需的最少硬币个数 dp [amount 1] * (amount 1) # 凑成金额 0 不需要硬币 dp[0] 0 # 遍历金额从 1 到 amount for i in range(1, amount 1): # 遍历每种硬币面额 for coin in coins: # 如果当前硬币面额小于等于当前金额 if coin i: # 更新 dp[i] dp[i] min(dp[i], dp[i - coin] 1) # 如果 dp[amount] 仍然是 amount 1说明无法凑成 return dp[amount] if dp[amount] ! amount 1 else -1测试用例测试用例 1输入coins [1, 2, 5], amount 11输出3测试用例 2输入coins [2], amount 3输出-1测试用例 3输入coins [1], amount 0输出0测试用例 4输入coins [1, 3, 4, 5], amount 7输出2总结本题是动态规划的经典问题主要考察对状态定义和状态转移方程的理解。通过动态规划我们可以高效地计算出凑成总金额所需的最少硬币个数。动态规划的核心思想是通过填充一个一维数组记录凑成每个金额所需的最少硬币个数。对于每个金额遍历每种硬币面额更新最少硬币个数。这种方法不仅适用于零钱兑换问题还可以应用于许多其他需要动态规划解决的问题例如完全背包问题、最少步数问题等。掌握动态规划的思想对于解决这类问题非常重要。