LC322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

算法的函数签名如下：

// coins 中是可选硬币面值，amount 是目标金额
int coinChange(vector<int>& coins, int amount);

1. 带备忘录的递归

class Solution {
public:
    vector<int> memo;
    
    int coinChange(vector<int>& coins, int amount) {
        memo = vector<int> (amount + 1, -666);
        // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
        return dp(coins, amount);
    }

    int dp(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        // 查备忘录，防止重复计算
        if (memo[amount] != -666)
            return memo[amount];

        int res = INT_MAX;
        for (int coin : coins) {
            // 计算子问题的结果
            int subProblem = dp(coins, amount - coin);

            // 子问题无解则跳过
            if (subProblem == -1) continue;
            // 在子问题中选择最优解，然后加一
            res = min(res, subProblem + 1);
        }
        // 把计算结果存入备忘录
        memo[amount] = (res == INT_MAX) ? -1 : res;
        return memo[amount];
    }
};

很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。

我们来分析这段代码的 时间复杂度 和 空间复杂度。这段代码是一个典型的 动态规划 + 备忘录 解法，用于解决 零钱兑换问题（给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少硬币数）。

---

1.1 时间复杂度分析

问题规模

• 假设硬币数量为 (k)（即 coins.size()），目标金额为 (n)（即 amount）。

递归树分析

• 每次递归调用 dp(coins, amount - coin)，会尝试用每一种硬币去减少 amount，直到 amount 减到 0 或负数。
• 最坏情况下，递归树的深度为 (n)（每次减去 1），每一层的分支数为 (k)（硬币的数量）。

备忘录优化

• 使用备忘录 memo 避免了重复计算，每个子问题只会被计算一次。
• 总共有 (n) 个子问题（amount 从 1 到 (n)），每个子问题需要遍历 (k) 种硬币。

总时间复杂度

• 每个子问题的计算复杂度为 (O(k))。
• 总共有 (n) 个子问题。
• 因此，总时间复杂度为：\(T(n, k) = O(n \times k)\)

---

1.2 空间复杂度分析

备忘录空间

• 备忘录 memo 的大小为 (n + 1)（amount 从 0 到 (n)），因此空间复杂度为 (O(n))。

递归栈空间

• 递归调用栈的深度最坏情况下为 (n)（每次减去 1），因此递归栈的空间复杂度为 (O(n))。

总空间复杂度

• 备忘录和递归栈的空间复杂度均为 (O(n))，因此总空间复杂度为：\(S(n) = O(n)\)

---

总结

• 时间复杂度 \(O(n \times k)\) 其中 (n) 是目标金额，(k) 是硬币数量。
• 空间复杂度：\(O(n)\) 主要用于存储备忘录和递归调用栈。