LeetCode322：零钱兑换

本文主要是介绍LeetCode322：零钱兑换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

代码

/*可以抽象为装满这个背包最少需要的物品数量 dp[j]：表示装满容量为j的背包最少需要dp[j]个物品递推公式：dp[j] = min(dp[j],dp[j-coins[i]]+1)便利顺序：for (int coin : coins) {for (int j = coin; j <= amount; j++) 
*/class Solution {
public:int coinChange(vector<int>& coins, int amount) {int Max = amount + 1;vector<int> dp(amount + 1, Max);  //min的时候初始化为Maxdp[0] = 0;for (int coin : coins) {for (int j = coin; j <= amount; j++) {if (j >= coin)dp[j] = min(dp[j], dp[j - coin] + 1);}}if (dp[amount] == Max) return -1;return dp[amount];}
};

这篇关于LeetCode322：零钱兑换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---