代码随想录第四十四天打卡

322. 零钱兑换

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

这句话结合本题 大家要好好理解。

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili

代码随想录

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for (int i=1;i<=amount;i++){
            for (int j=0;j<coins.size();j++){
                if (i>=coins[j] && dp[i-coins[j]]!=INT_MAX)
                dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        if (dp[amount]==INT_MAX)return -1;
        else return dp[amount];
    }
};

279.完全平方数

本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做

视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili

代码随想录

class Solution {
public:
    int numSquares(int n) {
        vector<int>dp(n+1,INT_MAX);
        dp[0]=0;
        for (int i=1;i*i<=n;i++){//遍历物品
            for (int j=1;j<=n;j++){//遍历背包
                if (j<i*i)continue;
                if (dp[j-i*i]!=INT_MAX)dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        }
        if (dp[n]==INT_MAX)return -1;
        else return dp[n];
    }
};

139.单词拆分

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili

代码随想录

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string>wordset(wordDict.begin(),wordDict.end());
        vector<bool>dp(s.size()+1,false);
        dp[0]=true;
        for (int i=0;i<=s.size();i++){//遍历背包
            for (int j=0;j<i;j++){//遍历物品
                string word=s.substr(j,i-j);
                if (wordset.find(word)!=wordset.end() && dp[j])dp[i]=true;
            }
        }
        return dp[s.size()];
    }
};

总结

感觉这道题不是传统的遍历物品。