322. 零钱兑换#

// 方法一：朴素递归（会超时）
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 边界情况：目标金额为 0 时，不需要任何硬币
        if (amount == 0) return 0;
        // 边界情况：金额变成负数，说明当前选择路径无效
        if (amount < 0) return -1;

        // min 记录当前金额的最小硬币数，先初始化为极大值表示“尚未找到方案”
        int min = Integer.MAX_VALUE;
        // 枚举每一种硬币，尝试把它作为当前要用的一枚硬币
        for (int coin : coins) {
            // 递归求解“剩余金额 amount - coin”的最优解
            int subResult = coinChange(coins, amount - coin);
            // 只有子问题可达（>=0）时，当前路径才有效
            if (subResult >= 0) {
                // 当前方案硬币数 = 子问题硬币数 + 1（加上当前这枚）
                min = Math.min(min, subResult + 1);
            }
        }

        // 若 min 仍是初始极大值，表示无解，返回 -1；否则返回最小硬币数
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

// 方法二：记忆化递归
class Solution {
    // memo[a] 记录凑出金额 a 的最优解：-2 表示未计算，-1 表示无解，其他非负数表示最少硬币数
    private int[] memo;

    public int coinChange(int[] coins, int amount) {
        // 申请缓存数组，下标 0..amount
        memo = new int[amount + 1];
        // 初始化为 -2，表示“该金额状态尚未被递归计算过”
        Arrays.fill(memo, -2);  // 用-2表示未计算过
        // 从目标金额开始递归搜索
        return helper(coins, amount);
    }

    private int helper(int[] coins, int amount) {
        // 边界情况：刚好凑到 0，说明当前路径合法且不需再加硬币
        if (amount == 0) return 0;
        // 边界情况：金额小于 0，说明超出了目标，路径无效
        if (amount < 0) return -1;
        // 若该状态已经算过，直接返回缓存结果，避免重复计算
        if (memo[amount] != -2) return memo[amount];

        // min 保存当前金额 amount 的最小硬币数
        int min = Integer.MAX_VALUE;
        // 逐个尝试使用每种硬币
        for (int coin : coins) {
            // 递归求解剩余金额
            int subResult = helper(coins, amount - coin);
            // 仅当剩余金额可凑出时才更新答案
            if (subResult >= 0) {
                // 当前候选解 = 子问题解 + 当前硬币 1 枚
                min = Math.min(min, subResult + 1);
            }
        }

        // 将当前金额的结果写入缓存：无解存 -1，有解存最少硬币数
        memo[amount] = min == Integer.MAX_VALUE ? -1 : min;
        // 返回缓存值
        return memo[amount];
    }
}

// 方法三：动态规划（最终优化版本）
class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] 表示凑出金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];
        // 初始化为 amount+1（不可能达到的上界），便于后续取最小值
        Arrays.fill(dp, amount + 1);  // 初始化为一个不可能的大数
        // 基础状态：凑出金额 0 需要 0 枚硬币
        dp[0] = 0;

        // 从小到大计算每个金额 i 的最优解
        for (int i = 1; i <= amount; i++) {
            // 枚举可用硬币，尝试作为“最后一枚硬币”
            for (int coin : coins) {
                // 只有当硬币面值不超过当前金额时才可使用
                if (i >= coin) {
                    // 状态转移：dp[i] = min(dp[i], dp[i-coin] + 1)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 若 dp[amount] 仍大于 amount，说明无解；否则返回最优值
        return dp[amount] > amount ? -1 : dp[amount];
    }
}