零钱兑换（DP）

给你一个整数数组 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

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1,amount + 1);
        dp[0] = 0;
        for(int c : coins){
            for(int i = c; i <= amount; i++){
                dp[i] = min(dp[i], dp[i - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

vector<int> dp(amount + 1, amount + 1);

创建一个 dp 数组，大小为 amount + 1。dp[i] 表示组成金额 i 所需的最少硬币数。

由于我们要找一个最小值，所以初始化所有 dp[i] 为 amount + 1，因为coin>=1，不可能会有这个值，但这可以表示我们还没有找到一个解。

for (int coin : coins)：

对每一个硬币 coin，我们遍历从 coin 到 amount 的所有金额 i，更新 dp[i]（小于coin的不成立）

for (int i = coin; i <= amount; i++)：

对于每个金额 i，我们可以选择将当前硬币 coin 添加到组成金额 i - coin 的解上，从而更新 dp[i] 为 dp[i] = min(dp[i], dp[i - coin] + 1)，表示最少硬币数的更新。

return dp[amount] > amount ? -1 : dp[amount];

如果 dp[amount] 仍然大于 amount，说明我们没有找到一个有效的解，因此返回 -1。

原文地址：https://blog.csdn.net/Ct314/article/details/143697136

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！