动态规划中等2 种解法

#322零钱兑换

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

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

解题主线

自顶向下定义 solve(remain) 为凑出剩余金额所需的最少硬币数，并缓存每个 remain。

自底向上令 dp[value] 表示凑出 value 的最少硬币数，从 dp[0] = 0 逐步转移。

amount + 1 大于任何可行解的硬币数，可作为安全的不可达哨兵。

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

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

时间复杂度

O(amount × c)，c 为硬币面额数量

空间复杂度

O(amount)，用于 memo 与最坏递归栈

322. 零钱兑换 · 自顶向下记忆化搜索

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) {
        if (remain < 0) return -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);
            }
        }
        int answer = minimum == Integer.MAX_VALUE ? -1 : minimum;
        memo.put(remain, answer);
        return answer;
    }
}

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

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

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

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

时间复杂度

O(amount × c)，c 为硬币面额数量

空间复杂度

O(amount)

322. 零钱兑换 · 自底向上动态规划

java

import java.util.Arrays;

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

        int unreachable = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, unreachable);
        dp[0] = 0;
        for (int value = 1; value <= amount; value++) {
            for (int coin : coins) {
                if (coin <= value) {
                    dp[value] = Math.min(dp[value], dp[value - coin] + 1);
                }
            }
        }
        return dp[amount] == unreachable ? -1 : dp[amount];
    }
}

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

边界与易错点

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

整理来源

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

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