LeetCode 322 - 零钱兑换 (Python3|Go) Coin Change - 后端

答案：本题可通过动态规划（DP）求解，核心思路是定义一个数组 dp，其中 dp[i] 表示凑出金额 i 所需的最少硬币数量。通过遍历所有金额状态和硬币面值，逐步更新 dp 数组，最终根据 dp[amount] 的值返回结果。

方法思路

初始化 DP 数组：
dp 数组的大小为 amount + 1，初始值设为 amount + 1（表示不可达），因为最多需要 amount 个 1 元硬币。
dp[0] = 0，表示金额 0 无需任何硬币。
状态转移：
对于每个金额 i（从 1 到 amount），遍历每个硬币面值 coin：
如果 i >= coin，则 dp[i] 可以更新为 min(dp[i], dp[i - coin] + 1)，即选择当前硬币后的最少硬币数。
返回结果：
如果 dp[amount] 仍为初始值 amount + 1，说明无法凑出，返回 -1。
否则返回 dp[amount]。

解决代码from typing import Listclass Solution: def coinChange(self, coins: List[int], amount: int) -> int: # 初始化 dp 数组，dp[i] 表示凑出金额 i 所需的最少硬币数 dp = [amount + 1] * (amount + 1) dp[0] = 0 # 金额 0 无需硬币 for i in range(1, amount + 1): for coin in coins: if i >= coin: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1func coinChange(coins []int, amount int) int { // 初始化 dp 数组 dp := make([]int, amount+1) for i := range dp { dp[i] = amount + 1 } dp[0] = 0 // 金额 0 无需硬币 for i := 1; i <= amount; i++ { for _, coin := range coins { if i >= coin { dp[i] = min(dp[i], dp[i-coin]+1) } } } if dp[amount] == amount+1 { return -1 } return dp[amount]}func min(a, b int) int { if a < b { return a } return b}代码解释

Python：
dp 数组初始化为 amount + 1，表示不可达状态。
双重循环遍历金额和硬币面值，更新 dp[i] 为最小值。
最后检查 dp[amount] 是否被更新，返回结果或 -1。
Go：
类似 Python，使用 make 初始化 dp 数组。
通过 min 函数辅助更新最小值。
逻辑与 Python 一致，确保正确处理边界情况。

此方法高效地利用动态规划避免了重复计算，时间复杂度为 O(n × amount)，空间复杂度为 O(amount)。

LeetCode 322 - 零钱兑换 (Python3|Go) Coin Change

您可能感兴趣问答

Collapsible

热门标签

热点问答