class Solution { public: int coinChange(vector<int>& coins, int amount) { int len=coins.size(); int dp[100086]; memset(dp,-1,sizeof(dp));//先初始化为-1，表示没有组合情况 dp[0]=0; for(int i=1;i<=amount;i++) { for(int j=0;j<len;j++) { if(i>=coins[j]) { if(dp[i-coins[j]]!=-1) { if(dp[i]==-1) dp[i]=dp[i-coins[j]]+1;//第一次直接改成值 else dp[i]=min(dp[i],dp[i-coins[j]]+1);//后面就要开始比较大小获取最小硬币数量 } } } } return dp[amount]; } };
class Solution { public: int change(int amount, vector<int>& coins) { long long dp[5005]; memset(dp,0,sizeof(dp)); int len=coins.size(); dp[0]=1; for(int i=0;i<len;i++)硬币循环放外面 { for(int j=0;j<=amount;j++) { if(dp[j]!=0&&j+coins[i]<=amount) dp[j+coins[i]]+=dp[j]; } } return dp[amount]; } };
原文：https://www.cnblogs.com/Charls/p/12694854.html