322.Coin Change
min
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,amount+1);
if(coins.size()==0) return -1;
dp[0]=0;
for(int i=1;i<=amount;++i) {
for(int c :coins) {
dp[i] = c<=i? min(dp[i],dp[i-c]+1):dp[i];
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
//我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：
//dp[i] = min(dp[i], dp[i - coins[j]] + 1);
//其中coins[j]为第j个硬币，
//而i - coins[j]为钱数i减去其中一个硬币的值，
//剩余的钱数在dp数组中找到值，
//然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组。