今天继续学习动规解决完全背包问题。

322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

思路：

1.本题因为每种硬币数量无线，可以看出是一道完全背包问题，总金额即为背包重量，每一种硬币即为物品。

2.首先想dp数组含义，dp[j]代表装满容量为j的背包所需要的最少物品个数

3.然后想递推公式，对于当前物品有两种选择，放或者不放，放入背包的话即为dp[j - coins[i]] + 1（因为要求的是最少物品个数，因此是加1！），不放入背包即为dp[j]，对这两者取最小值即为递推公式

4.然后想初始化，题目示例已经告诉我们dp[0] = 0，而递推公式中涉及取最小值，因此其他我们初始化为INT_MAX

5.最后想遍历顺序，因为本题要求的是最少数量，而元素的顺序并不会影响装满背包的最少物品数量，因此无论先物品还是先背包都可以。

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++){
            for(int j = coins[i]; j <= amount; j++){
                if(dp[j - coins[i]] != INT_MAX){
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

启发：

1.本题尽管基本思路和代码都相对好想，但还是会有细节的问题。在第一次提交后报了如下错误：

 将报错示例代入后就会发现问题：如果在遍历过程中dp[j - coins[i]]依旧等于INT_MAX，说明对于当前物品，当前背包没办法装满，对于这种情况我们应当跳过，因此在for循环取值时仍然需要一个条件判断语句来判断dp[j - coins[i]]是否等于INT_MAX。

279.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

思路：

1.本题实质上和上一道题一模一样，背包容量即为给出的n，物品是各个完全平方数。因此详细思路就不再一一列出。

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 = i*i; j <= n; j++){
                if(dp[j - i * i] != INT_MAX){
                    dp[j] = min(dp[j], dp[j - i * i] + 1);
                }
            }
        }

        return dp[n];
    }
};

启发：

1.本题仍然有那么一些上一题没有的细节上的东西。如for循环时，i，j各自的循环条件是什么？j代表背包容量因此很容易就能想到j <= n，而对于i，一开始想的是不设限制，直到某个具体条件时直接让循环break，但这样就有一个问题：这个具体条件是什么？我们要求最少数量，但除非遍历结束不然也不能保证你当前已经取到的值就是最小数量。但有一点是肯定的，因为要用完全平方数来组成我们的n，因此该完全平方数显然不能大于n，因此i的循环条件为i * i <= n。

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

思路：

1.本题乍一看会先想到KMP算法，不过KMP算法的应用场景与本题相似但不完全相同，毕竟本题要看字典中的单词能否拼接成字符串。由于单词可以重复使用，我们可以将其抽象为一个完全背包问题，原字符串长度即为背包容量，字典中的每一个单词即为物品。

2.首先想dp数组含义。本题dp数组不同于之前所有的dp数组，因为本题要求的是是否能组成，并不单纯是求一个数值了，因此dp数组得设置为布尔类型，dp[i] = true 表示长度为i的字符串能够被字典中的单词构成。

3.然后想递推公式，本题递推公式也相对没那么好像，因为没有一个确切的公式。对于dp[i]能否被字典中的单词构成，我们得看前面的部分。此时假设前面一个位置为j，那么dp[i] = true的条件是dp[j] = true（即位置j及之前的元素能够被字典中的单词组成），且区间为 [j , i] 部分的字符串也能被字典中的单词组成。

4.然后想初始化，dp[0]一定得是true,因为后续都是由dp[0]推导出来的，其他的为false即可

5.然后想遍历顺序，本题对于元素的顺序实际上是有要求的，拿题目中的示例2举例子，只要有两个apple和一个pen就可以组成字符串，但是这三个字符串的组合不一定是我们要的字符串。因此本题实际上求的是排列数，我们必须要元素顺序也对应上我们的原字符串，所以要先遍历背包后遍历物品。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set(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 tmp = s.substr(j, i - j);
                if(dp[j] == true && set.find(tmp) != set.end()){
                    dp[i] = true;
                }
            }
        }

        return dp[s.size()];
    }
};

启发：

1.个人觉得似乎一旦涉及上字符串题目就会难很多（思路可能相对于代码都会稍微好一点），本题首次将dp数组设置为布尔变量容器，且用到了哈希表来作为字典辅助查询，递推公式的思想也十分巧妙，需要更进一步的理解。