动态规划中等2 种解法

#322零钱兑换

用给定面额的无限枚硬币凑出 amount，返回所需最少硬币数，无法凑成时返回 -1。

#数组#动态规划#记忆化搜索

原题

给你一个整数数组 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

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

查看原题

解题主线

自顶向下定义 solve(remain) 为凑出剩余金额所需的最少硬币数，并缓存每个 remain。
自底向上令 dp[value] 表示凑出 value 的最少硬币数，从 dp[0] = 0 逐步转移。
amount + 1 大于任何可行解的硬币数，可作为安全的不可达哨兵。

解法 1：自顶向下记忆化搜索

从 amount 尝试减去每种硬币，对所有可达子问题取最小值；memo 仅属于本次 coins 与 amount 调用。

时间复杂度： O(amount × c)，c 为硬币面额数量
空间复杂度： O(amount)，用于 memo 与最坏递归栈

JAVA

import java.util.HashMap;
import java.util.Map;

final class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || amount < 0) return -1;
        Map<Integer, Integer> memo = new HashMap<>();
        memo.put(0, 0);
        return solve(coins, amount, memo);
    }

    private int solve(int[] coins, int remain, Map<Integer, Integer> memo) {
        // remain 是当前子问题尚需凑出的金额，负数表示该选择不可达
        if (remain < 0) return -1;
        // 每个剩余金额只求解一次，缓存同时保存不可达结果 -1
        Integer cached = memo.get(remain);
        if (cached != null) return cached;

        int minimum = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subproblem = solve(coins, remain - coin, memo);
            // 不可达子问题不能参与加一和最小值比较
            if (subproblem >= 0) {
                minimum = Math.min(minimum, subproblem + 1);
            }
        }
        // MAX_VALUE 作为尚未发现可行组合的哨兵
        int answer = minimum == Integer.MAX_VALUE ? -1 : minimum;
        memo.put(remain, answer);
        return answer;
    }
}

实现提示

LeetCode 约束硬币面额均为正数；局部 memo 从根源上消除跨 coins 输入污染。

解法 2：自底向上动态规划

从金额 1 到 amount 填表，对每种不超过当前金额的硬币尝试由 dp[value - coin] 转移。

时间复杂度： O(amount × c)，c 为硬币面额数量
空间复杂度： O(amount)

JAVA

import java.util.Arrays;

final class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || amount < 0) return -1;

        // amount + 1 大于任一可行解的硬币数，用作不可达哨兵
        int unreachable = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, unreachable);
        // dp[value] 表示凑出 value 所需的最少硬币数
        dp[0] = 0;
        for (int value = 1; value <= amount; value++) {
            for (int coin : coins) {
                if (coin <= value) {
                    // 由已求出的 value - coin 状态追加一枚当前硬币
                    dp[value] = Math.min(dp[value], dp[value - coin] + 1);
                }
            }
        }
        // 哨兵未被更新说明目标金额不可达
        return dp[amount] == unreachable ? -1 : dp[amount];
    }
}

边界与易错点

旧实现把 memo 放在实例字段且只按 amount 建键；同一对象换一组 coins 再调用会错误复用旧结果，整理后 memo 每次公开调用重新创建。
递归遇到负剩余金额要返回 -1，且不能对不可达子问题执行加一。
本题是完全背包，每种面额可使用任意次。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q322_coinChange_fibonacci.java