零钱兑换

链接

直接用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)