《灵珠觉醒：从零到算法金仙的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