Coin Change

322. 零钱兑换

分析

定义状态：
- f[j]：表示凑成金额 j 所需的最少硬币个数
状态转移方程：
- 对于每个硬币面值 coins[i]，如果选择该硬币，那么金额 j 的状态可以由金额 j - coins[i] 转移而来：f[j] = min(f[j], f[j - coins[i]] + 1)，即当前金额的最优解为不选择当前硬币的解和选择当前硬币的解的较小值
初始化：
- f[0] = 0：凑成金额 0 所需的硬币数为 0
- 其他状态 f[j] 初始化为无穷大（设为一个较大的值 INF），表示尚未凑成
结果判断：
- 如果 f[amount] = INF ，表示无法凑成金额 amount，返回 -1
- 否则返回 f[amount]

时间复杂度

外层循环遍历硬币种类 O(n) ，内层循环遍历金额 O(amount) ，总复杂度为 O(n * amount)

空间复杂度

空间复杂度为 O(amount)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    int coinChange(vector<int>& coins, int amount)
    {
        int INF = 0x3f3f3f3f;  // 定义一个较大的值表示无穷大
        std::vector<int> f(amount + 1, INF);  // 初始化 DP 数组
        f[0] = 0;  // 金额为 0 时需要 0 个硬币

        for (int i = 0; i < coins.size(); ++i)  // 遍历每个硬币面值
        {
            for (int j = coins[i]; j <= amount; ++j)  // 遍历所有可能金额
            {
                f[j] = std::min(f[j], f[j - coins[i]] + 1);  // 状态转移
            }
        }

        if (f[amount] == INF)  // 如果金额无法凑成
            return -1;
        return f[amount];  // 返回最优解
    }
};