322 零钱兑换

一、题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

二、题解

思路：动态规划（完全背包）

1. 核心思路

由于每种硬币可以无限次使用，因此这是一个典型的完全背包问题。

定义 dp[i] 表示凑成金额 i 所需的最少硬币数。

对于每一个金额 i，尝试使用每一种硬币 coin。

如果当前金额能够使用该硬币（i >= coin），那么：

  • 先凑出 i - coin
  • 再放入一枚 coin

因此可以得到状态转移公式：

dp[i] = min(dp[i], dp[i - coin] + 1)

最终：

  • 如果 dp[amount] 没有更新，说明无法组成，返回 -1
  • 否则返回 dp[amount]

2. 具体步骤

  1. 定义 dp[i] 表示凑成金额 i 所需的最少硬币数。
  2. 初始化 dp[0] = 0，其余位置初始化为 amount + 1（表示无法到达）。
  3. 遍历金额 1 ~ amount。
  4. 对于每个金额，遍历所有硬币：
    • 如果 i >= coin，尝试更新： 
      dp[i] = min(dp[i], dp[i - coin] + 1)
  5. 最后判断 dp[amount] 是否仍为初始值：
    • 是，返回 -1
    • 否，返回 dp[amount]

3. 关键逻辑

状态定义：

dp[i]：凑成金额 i 所需的最少硬币数

初始化：

dp[0] = 0;

for (int i = 1; i <= amount; i++) {
    dp[i] = amount + 1;
}

这里使用 amount + 1 表示"无穷大"，避免使用 Integer.MAX_VALUE 导致加 1 时发生整数溢出。

状态转移：

if (i >= coin) {
    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}

含义：

  • 如果最后放入一枚 coin
  • 那么前面的金额就是 i - coin
  • 再加上当前这一枚硬币即可

所以：

dp[i] = dp[i - coin] + 1

不断取最小值即可得到最优解。

三、代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 1. 定义 dp 数组
        int[] dp = new int[amount + 1];

        // 2. 初始化
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }

        // 3. 动态规划
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 4. 返回结果
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

四、复杂度分析

时间复杂度：O(amount × n)

说明：

  • amount 个金额需要计算。
  • 每个金额都会遍历 n 种硬币。

因此总时间复杂度为：

O(amount × n)

其中：

  • amount 为目标金额
  • n 为硬币种类数量

空间复杂度：O(amount)

说明：

只使用了一个长度为 amount + 1 的一维 dp 数组，因此空间复杂度为：

O(amount)

评论