leetcode hot100【LeetCode 322. 零钱兑换】java实现

LeetCode 322. 零钱兑换

题目描述

给定不同面额的硬币和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少硬币数。如果不可能凑成总金额，则返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

Java 实现代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 初始化为一个较大的数
        dp[0] = 0; // 0元需要0个硬币
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

解题思路

这个问题可以通过动态规划来解决。我们定义一个数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数。

1. 初始化 dp 数组，将所有元素设置为 amount + 1（一个较大的数），除了 dp[0] 设置为 0，因为凑成 0 元不需要硬币。
2. 遍历从 1 到 amount 的每个金额 i。
3. 对于每个金额 i，遍历所有硬币面额 coin。
4. 如果当前金额 i 大于或等于硬币面额 coin，则更新 dp[i] 为 dp[i - coin] + 1 和当前 dp[i] 的最小值。
5. 最后，如果 dp[amount] 大于 amount，则表示无法凑成总金额，返回 -1；否则返回 dp[amount]。

复杂度分析

• 时间复杂度：O(amount * n)，其中 n 是硬币的数量，因为我们需要遍历每个金额和每种硬币。
• 空间复杂度：O(amount)，需要一个大小为 amount + 1 的数组 dp 来存储中间结果。