网站建设zvge惠州疫情最新情况

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

这题还是有点儿难度的，刚开始我想的是直接用回溯来做，虽然代码超时了，但是这里也附上我的代码，以儆效尤~

    void traverse(vector<int>& coins,int amount,long long sum,int temp){if(sum>amount) return;for(int i=0;i<coins.size();i++){sum+=coins[i];temp++;if(sum==amount){minl=min(minl,temp);}traverse(coins,amount,sum,temp);sum-=coins[i];temp--;}}int coinChange(vector<int>& coins, int amount) {if(amount==0)return 0;traverse(coins,amount,0,0);return minl==INT_MAX?-1:minl;}

结果不出意外，出意外额~

看了一下数据量，发现用回溯来做确实不太行，好，果断改策略，改用动态规划~

 int coinChange(vector<int>& coins, int amount){if(coins.size()==0)return -1;vector<int> dp(amount+1,amount+1);dp[0]=0;for(int i=1;i<=amount;i++){for(int j=0;j<coins.size();j++){if(i-coins[j]>=0){dp[i]=min(dp[i],dp[i-coins[j]]+1);}}}return dp[amount]==amount+1?-1:dp[amount];}

运行，ok，过了~

这题用动态规划可能还是有点儿难度，一刚开始我还在想状态方程怎么用在coins数组上，后来借鉴了一下别人的思路，用在amount上可能更容易写一点，好吧，我承认我是垃圾~

看了代码还是存在疑问的宝子可以评论区留言哦，私我也行，我们共同成长~