代码随想录第四十六天 | 322. 零钱兑换，279.完全平方数，139.单词拆分

322. 零钱兑换

看完想法：此处是求最小值，所以递推公式中含Min，即dp[j] = min(d[[j], dp[j - coins[i]] + 1)，初始化都为INT_MAX，且dp[0]  = 0。由于不是求组合数，所以物品和背包重量的遍历先后顺序都是可以的。此处要注意一个细节，如果是物品for外循环，背包从coins[j] 开始并且 j++，（之前有碰到j = bagweight, j--的，二者的区别是：j--是01背包，j++是完全背包；背包容量优先还需要判断j - weight[i] >=0,即背包有没有被装满，才进行dp滚动）

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        //选用外部遍历物品
        for(int i = 0; i<coins.size(); i++){
            for(int j = coins[i]; j <=amount; j++){
                //if需要考虑的是INT_MAX溢出的情况，我们可以把max换成amount+1
                dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
        if (dp[amount] == amount+1) return -1;
        return dp[amount];

279.完全平方数

看完想法：和零钱兑换如出一辙。dp[j]代表和为 j 的完全平方数的最少数量为 dp[j] 。初始化可以为0，因为题目不要求一定找到最小数量

int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // 遍历背包
            for (int j = 1; j * j <= i; j++) { // 遍历物品，每次j的平方不能超过背包大小
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];

139.单词拆分

看完想法：可以反过来想问题，列表中的字符串究竟能不能把给的字符串填满。所以定义dp[j]，j为字符串长度。这里因为涉及到了字符串的顺序（112构成字符串，121就不是原来的字符串了），所以要求排列数，即先遍历背包，再遍历物品

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 = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    //表明存在word且i的dp为true
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];