题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 18】。如果这个视频对你有帮助，欢迎一键三连！

一、递归搜索 + 保存计算结果 = 记忆化搜索

答疑

问：为什么不需要写 $\mathit{\text{dfs}}(i-1,c-\mathit{\text{coins}}[i])$ 呢？选了一个就不再选了，这样不行吗？

答：其实我们已经考虑这种情况了，先「选一个」，递归到 $\mathit{\text{dfs}}(i,c-\mathit{\text{coins}}[i])$，在这个递归中再「不选」，就能递归到 $\mathit{\text{dfs}}(i-1,c-\mathit{\text{coins}}[i])$ 了。也就是说，递归两次，我们就能表达出「选了一个就不再选」的逻辑。从这个例子，相信读者能体会到递归所蕴含的强大表达能力。

Python 解法1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, c: int) -> int:
            if i < 0:
                return 0 if c == 0 else inf
            if c < coins[i]:  # 只能不选
                return dfs(i - 1, c)
            # 不选 vs 继续选
            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)

        ans = dfs(len(coins) - 1, amount)
        return ans if ans < inf else -1

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector memo(n, vector<int>(amount + 1, -1)); // -1 表示没有计算过

        // lambda 递归函数
        auto dfs = [&](this auto&& dfs, int i, int c) -> int {
            if (i < 0) {
                return c == 0 ? 0 : INT_MAX / 2; // 除 2 防止下面 + 1 溢出
            }
            int& res = memo[i][c]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            if (c < coins[i]) { // 只能不选
                return res = dfs(i - 1, c);
            }
            // 不选 vs 继续选
            return res = min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
        };

        int ans = dfs(n - 1, amount);
        return ans < INT_MAX / 2 ? ans : -1;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$，其中 $n$ 为 $\mathit{\text{coins}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$。

二、1:1 翻译成递推

Python 解法3

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        f = [[inf] * (amount + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(coins):
            for c in range(amount + 1):
                if c < x:
                    f[i + 1][c] = f[i][c]
                else:
                    f[i + 1][c] = min(f[i][c], f[i + 1][c - x] + 1)
        ans = f[n][amount]
        return ans if ans < inf else -1

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(n + 1, vector<int>(amount + 1, INT_MAX / 2)); // 除 2 防止下面 + 1 溢出
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    f[i + 1][c] = f[i][c];
                } else {
                    f[i + 1][c] = min(f[i][c], f[i + 1][c - coins[i]] + 1);
                }
            }
        }
        int ans = f[n][amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$，其中 $n$ 为 $\mathit{\text{coins}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$。

三、空间优化：两个数组（滚动数组）

Python 解法5

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        f = [[inf] * (amount + 1) for _ in range(2)]
        f[0][0] = 0
        for i, x in enumerate(coins):
            for c in range(amount + 1):
                if c < x:
                    f[(i + 1) % 2][c] = f[i % 2][c]
                else:
                    f[(i + 1) % 2][c] = min(f[i % 2][c], f[(i + 1) % 2][c - x] + 1)
        ans = f[n % 2][amount]
        return ans if ans < inf else -1

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(2, vector<int>(amount + 1, INT_MAX / 2));
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    f[(i + 1) % 2][c] = f[i % 2][c];
                } else {
                    f[(i + 1) % 2][c] = min(f[i % 2][c], f[(i + 1) % 2][c - coins[i]] + 1);
                }
            }
        }
        int ans = f[n % 2][amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$，其中 $n$ 为 $\mathit{\text{coins}}$ 的长度。
• 空间复杂度：$\mathcal{O}(\mathit{\text{amount}})$。

四、空间优化：一个数组

好比在一面墙上画画，原来这面墙画的是 $f[i]$，现在要画一副新的画，把原来的画覆盖掉，新的画叫做 $f[i+1]$。

在循环的过程中：

• 对于 $c<x$ 的状态，转移方程是 $f[i+1][c]=f[i][c]$，这说明原来画的内容保持不变，空间优化后是 $f[c]=f[c]$，这个赋值是多余的。所以可以从 $c=x$ 开始循环。
• 对于 $c\ge x$ 的状态，转移方程是 $f[i+1][c]=min(f[i][c],f[i+1][c-x]+1)$，其中 $f[i][c]$ 就地取材，$f[i+1][c-x]$ 是新画的内容，从这面墙的下标 $c-x$ 处取到，所以空间优化后就是 $f[c]=min(f[c],f[c-x]+1)$。

关于先枚举物品还是先枚举体积的讨论，见 377. 组合总和 Ⅳ 我的题解 中的「答疑」。

Python 解法7

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        f = [0] + [inf] * amount
        for x in coins:
            for c in range(x, amount + 1):
                f[c] = min(f[c], f[c - x] + 1)
        ans = f[amount]
        return ans if ans < inf else -1

C++ 解法7

// C++ 版待补充

C++ 解法8

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, INT_MAX / 2);
        f[0] = 0;
        for (int x : coins) {
            for (int c = x; c <= amount; c++) {
                f[c] = min(f[c], f[c - x] + 1);
            }
        }
        int ans = f[amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$，其中 $n$ 为 $\mathit{\text{coins}}$ 的长度。
• 空间复杂度：$\mathcal{O}(\mathit{\text{amount}})$。

五、BFS 做法

设当前凑成的总金额为 $s$。添加一枚硬币 $\mathit{\text{coins}}[i]$ 后，$s$ 变成了 $s+\mathit{\text{coins}}[i]$。

把总金额当作节点编号，从 $s$ 到 $s+\mathit{\text{nums}}[i]$ 连一条有向边，我们可以得到一张有向图。

本题相当于：

• 计算从起点 $0$ 到终点 $\mathit{\text{amount}}$ 的最短路长度。

这可以用 BFS 解决。

下面代码用双数组实现 BFS，原理请看【基础算法精讲 13】。

Python 解法9

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        q = [0]
        vis = [True] + [False] * amount
        step = 0

        while q:
            nxt = []
            for s in q:
                if s == amount:
                    return step
                for x in coins:
                    t = s + x
                    if t <= amount and not vis[t]:  # 之前没有访问过
                        vis[t] = True  # 避免重复访问
                        nxt.append(t)
            q = nxt
            step += 1

        return -1

C++ 解法9

// C++ 版待补充

C++ 解法10

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> q = {0};
        vector<int8_t> vis(amount + 1);
        vis[0] = true;

        for (int step = 0; !q.empty(); step++) {
            auto tmp = move(q);
            for (int s : tmp) {
                if (s == amount) {
                    return step;
                }
                for (int x : coins) {
                    if (s <= amount - x && !vis[s + x]) { // 之前没有访问过
                        vis[s + x] = true; // 避免重复访问
                        q.push_back(s + x);
                    }
                }
            }
        }

        return -1;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\cdot \mathit{\text{amount}})$，其中 $n$ 为 $\mathit{\text{coins}}$ 的长度。
• 空间复杂度：$\mathcal{O}(\mathit{\text{amount}})$。

专题训练

1. 动态规划题单的「§3.2 完全背包」。
2. 图论题单的「§1.3 图论建模 + BFS 最短路」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府