322.零钱兑换
我一开始想用二维dp，但是错了。
标答用的一维dp。
int coinChange(int* coins, int coinsSize, int amount){
int dp[amount+1];
for(int i=1;i<=amount;i++)
dp[i]=amount+1;
这里的初始化，我用memset不太行。部分用例没过。
dp[0]=0;
这里容易错。
for(int i=1;i<=amount;i++){
for(int j=0;j
if(i>=coins[j])
dp[i]=fmin(dp[i],dp[i-coins[j]]+1);
}
}
return dp[amount]>amount?-1:dp[amount];
}
279.完全平方数
这题和322，非常像，我自己也能做出来，就是每个数可出现多次的组合，求最少元素的组合。
那就直接套公式了呗。
int numSquares(int n){
int dp[n+1];
for(int i=0;i<=n;i++){
dp[i]=n+1;
}
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j*j<=i;j++){
dp[i]=fmin(dp[i-j*j]+1,dp[i]);
}
}
return dp[n]；
}