322. 零钱兑换

Problem: 322. 零钱兑换

思路

直接看代码注释

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //dp[i] 表示每i元需要最少dp[i]个硬币凑足
        //初始化 dp[0] = 0;
        //背包[0-amount] 
        //物品coins
        //遍历顺序 组合问题 先背后物 
        //完全背包 背包顺序遍历
        vector<int> dp(amount+1,INT_MAX);
        dp[0] = 0;
        for(int j = 0; j <= amount; j++) {
            for(int i = 0; i < coins.size(); i++) {
                // 凑不足
                if(j>=coins[i]) {
                    if(dp[j-coins[i]] == INT_MAX) continue;
                    // min(要此硬币凑足的最少个数,不要此硬币时凑足的最少个数) 
                    dp[j] = min(dp[j-coins[i]]+1,dp[j]);
                 }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};