通过对比完全背包和01背包的leetcode hot100中几个小题目，明确应用场景，以及代码书写的遍历顺序。
完全背包问题
完全背包指的是每件物品可以重复被使用，放入背包中。
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 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1);dp[0] = 0;int n = coins.size();for (int i = 1; i <= amount; i++) {for (int j = 0; j < n; j++) {if (coins[j] <= i) {dp[i] = min(dp[i], dp[i - coins[j]] + 1);}}}if (dp[amount] > amount) return -1;return dp[amount];}
};01背包问题
01背包指的是每件最多只能被使用一次，放入背包中。
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
class Solution {
public:bool canPartition(vector<int>& nums) {int n = 20000;vector<bool> dp(n + 1, false);dp[0] = true;int sum = 0;for (int j = 0; j < nums.size(); j++) {sum += nums[j];for (int i = n; i >= 1; i--) {if (i >= nums[j] && dp[i - nums[j]]) {dp[i] = true;}}}if (sum & 1) return false;return dp[sum >> 1];}
};完全背包-需要联想下
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
这个题目需要把词典的每个单词想成一件物品，而字符串s当成背包。完全背包问题。最开始想的第一种方法居然是构造前缀树Trie，进行搜索。
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.length();vector<bool> dp(len + 1, false);// 完全背包dp[0] = true;int n = wordDict.size();for (int i = 1; i <= len; i++) {for (int j = 0; j < n; j++) {int t = wordDict[j].size();if (t <= i && dp[i - t] && s.substr(i - t, t) == wordDict[j]) {dp[i] = true;break;}}}return dp[len];}
};
