零钱兑换
直接用dfs怕是要超时,有一种巧妙的思路
设一个大小为amount的数组dp,(全部初始化为INT_MAX)对于coins的每一个值,dp[coin]都设为1, 然后,我们可以设想一下,对于某一个i,dp[k]!=INT_MAX, 那么dp[i]是不是有可能等于dp[k]+1(也有可能dp[i]本身就比较小)
既然这样,那么我们让i从1遍历到amount,就能找到最终答案了
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,INT_MAX);
dp[0]=0;
for(int i=0;i<coins.size();i++){
if(coins[i]<=amount)
dp[coins[i]]=1;
}
for(int i=1;i<=amount;i++){
for(int coin:coins){
if(i>coin&&dp[i-coin]!=INT_MAX){
dp[i]=min(dp[i], dp[i-coin] + 1);
}
}
}
if(dp[amount]!=INT_MAX) return dp[amount];
return -1;
}
};
时间复杂度:O(amount*k)
空间复杂度:O(amount)