《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（39）玲珑棋局摆硬币 - 零钱兑换（完全背包）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（39）玲珑棋局摆硬币 - 零钱兑换（完全背包）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的玲珑棋局，棋局中摆放着各种面值的硬币。棋局的入口处有一块巨大的石碑，上面刻着一行文字：“欲破此局，需以玲珑棋局之力，摆硬币，完全背包显真身。”

哪吒定睛一看，石碑上还有一行小字：“给定硬币面值[1, 2, 5]和目标金额11，最少需要3枚硬币（5 + 5 + 1）。”哪吒心中一动，他知道这是一道关于零钱兑换的难题，需要通过完全背包的动态规划方法，找到最少的硬币数量。

暴力解法：玲珑棋局的初次尝试

哪吒心想：“要找到最少的硬币数量，我可以逐个硬币尝试。”他催动玲珑棋局之力，通过递归的方式，枚举所有可能的硬币组合，试图找到最少的硬币数。

int coinChange(vector<int>& coins, int amount) {
   
    if (amount == 0) return 0;
    int minCoins = INT_MAX;
    for (int coin : coins) {
   
        if (coin <= amount) {
   
            int result = coinChange(coins, amount - coin);
            if (result != -1) {
   
                minCoins = min(minCoins, result + 1);
            }
        }
    }
    return minCoins == INT_MAX ? -1 : minCoins;
}

哪吒成功地找到了最少的硬币数量，但玲珑棋局的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当目标金额很大时，灵力消耗巨大。

C++语法点

在C++中，完全背包问题通常使用动态规划来解决。以下是一些重要特性：

• 动态规划数组：

  • 使用vector<int>来表示动态规划数组。
  • 常用操作：
    • dp[i]：表示金额为i时的最少硬币数。
    • 初始化动态规划数组：vector<int> dp(amount + 1, INT_MAX)。

• 循环结构：

  • 外层循环遍历硬币面值。
  • 内层循环遍历目标金额。

高阶优化：完全背包的智慧

哪吒元神中突然浮现金色铭文——「玲珑棋局摆硬币，完全背包显真身」。他意识到，可以通过完全背包的动态规划方法，优化零钱兑换问题的解决过程。

哪吒决定使用动态规划，创建一个数组dp，其中dp[i]表示金额为i时的最少硬币数。通过初始化dp[0] = 0，然后遍历每个硬币面值，更新dp数组。通过这种方式，他成功地找到了最少的硬币数量，而且灵力消耗大幅减少。

int coinChange(vector<int>& coins, int amount) {
   
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int coin : coins) {
   
        for