vvrf / DSA.log

问题拆解

给一组硬币面额，每种可以无限次使用，问凑出金额 amount 最少要几枚硬币，凑不出返回 -1。

贪心地每次拿最大面额是不行的：面额 [1, 3, 4] 凑 6，贪心给出 4 + 1 + 1 三枚，而最优解是 3 + 3 两枚。局部最优在这里不能保证全局最优，得老老实实枚举所有可能。

关键观察和爬楼梯如出一辙：凑出金额 i 的最后一枚硬币，必然是某个面额 coin，去掉它之后剩下的部分就是“凑出 i - coin 的最优解”。区别在于爬楼梯问的是走法总数（各来源求和），这里问的是最少枚数（各来源取 min）：

dp[i] = min(dp[i - coin] + 1)，对每个 coin 取最小

求最值的 DP 和计数 DP 共享同一套“枚举最后一步”的骨架，换的只是聚合方式：求和改取 min，初值 0 改成无穷大。

自底向上的完全背包

每种硬币可以重复选，这就是完全背包。自底向上从 dp[0] = 0 出发，逐个金额往上推，每个金额尝试所有面额。“无穷大”不用真的取 Integer.MAX_VALUE——那会在 + 1 时溢出成负数，用 amount + 1 这个不可能达到的值就够了（每枚硬币面额至少为 1，最多用 amount 枚）。

public int coinChange(int[] coins, int amount) {
    int inf = amount + 1; // 不可能达到的值，兼当“凑不出”标记
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, inf);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] >= inf ? -1 : dp[amount];
}

def coinChange(coins: List[int], amount: int) -> int:
    inf = amount + 1  # 不可能达到的值，兼当“凑不出”标记
    dp = [inf] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return -1 if dp[amount] >= inf else dp[amount]

func coinChange(coins []int, amount int) int {
    inf := amount + 1 // 不可能达到的值，兼当“凑不出”标记
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = inf
    }
    dp[0] = 0
    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i {
                dp[i] = min(dp[i], dp[i-coin]+1)
            }
        }
    }
    if dp[amount] >= inf {
        return -1
    }
    return dp[amount]
}

pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let amount = amount as usize;
    let inf = (amount + 1) as i32; // 不可能达到的值，兼当“凑不出”标记
    let mut dp = vec![inf; amount + 1];
    dp[0] = 0;
    for i in 1..=amount {
        for &coin in &coins {
            let coin = coin as usize;
            if coin <= i {
                dp[i] = dp[i].min(dp[i - coin] + 1);
            }
        }
    }
    if dp[amount] >= inf { -1 } else { dp[amount] }
}

dp[0] = 0 是整个递推的种子：凑出 0 元需要 0 枚硬币。若某个 dp[i - coin] 仍是无穷大，说明那个金额凑不出来，min 会自动忽略这条来路——这正是用大初值而不是 -1 标记“不可达”的好处，无须额外判断。最后 dp[amount] 还停在无穷大，才翻译成 -1 返回。

顺带一提，这题不需要关心硬币的选取顺序（3 + 4 和 4 + 3 是同一种方案数没关系，反正只记枚数），所以两层循环谁内谁外都对；换成“组合总数”类问题时循环顺序才会变得敏感。

复杂度

指标	复杂度	原因
时间	`O(amount × k)`	每个金额尝试 k 种面额
空间	`O(amount)`	一维 dp 表

可以迁移的模式

“枚举最后一步的来源”既能做计数 DP，也能做最值 DP，区别只在求和还是取 min/max；
求最小值时初值设为“不可能达到的大数”，不可达状态会被 min 自然屏蔽，别用 INT_MAX 以免加一溢出；
每种物品可无限选、金额从小到大正序遍历，就是完全背包的标准姿势。

分清“问几种方法”还是“问最少多少”，是拿到一道 DP 题后要做的第一个判断。