本文主要是介绍自学动态规划——零钱兑换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
零钱兑换
322. 零钱兑换 - 力扣(LeetCode)
注意几个关键的地方:
- 因为每次都是找min,所以我们不能将所有元素都初始化为0,不然最后结果一定是0,这里我设置为0x3f3f3f3f,表示无解。
- 当
amount==0
的时候,此时的最小硬币个数应该是0,所以dp[0]=0
,是有解的,不能设置为dp[0]=0x3f3f3f3f
AC:
int coinChange(vector<int>& coins, int amount)
{const int N=0x3f3f3f3f;vector<int>dp(amount+1,N); //dp表示凑成amount的最少硬币个数dp[0]=0;for(int i=0;i<coins.size();i++)for(int j=coins[i];j<=amount;j++)dp[j]=min(dp[j],dp[j-coins[i]]+1);if(dp[amount]==N) return -1;return dp[amount];
}
这篇关于自学动态规划——零钱兑换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!