写在前
背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。
True/False问题核心公式：
dp[i] = dp[i] || dp[i-num]
Tips:
- 如果是完全背包，即数组中的元素可重复使用，
nums放在外循环，target在内循环。且内循环正序。 - 如果是0-1背包，即数组中的元素不可重复使用，
nums放在外循环，target在内循环，且内循环倒序； - 如果组合问题（完全背包问题）需考虑元素之间的顺序，需将
target放在外循环，将nums放在内循环，（如T377零钱兑换、T70爬楼梯、T139单词拆分）。
ps：不涉及顺序的完全背包问题，nums和target在内外循环都可以，但建议nums外循环，target内循环。
1.分割等和子集 （416-中）
题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路：动态规划：本题本质是01背包问题（每个数只用一次！），即遍历得到一个数有两个状态：加入结果，或者不加入结果。dp[i]表示前i个数中是否能构成sum/2。为保证合法性初始条件dp[0] = true。
代码：动态规划
public boolean canPartition(int[] nums) {
int sum = sumArrays(nums);
// 一定不能拆分
if (sum % 2 != 0) return false;
int W = sum / 2;
boolean[] dp = new boolean[W + 1];
dp[0] = true;
for (int num : nums) {
// 倒叙遍历结果，防止覆盖
for (int i = W; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[W];
}
private int sumArrays(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
2.单词拆分（139-中）
题目描述：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
思路：动态规划：完全背包问题（字典单词可进行多次使用）
法1：求解【顺序的完全背包问题】时，对nums的迭代应该放在最里层，对target的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。其中，dp[i]表示字符串s的前i个字符能否拆分成wordDict。 状态转移方程：dp[i] = dp[i] || dp[i - len]。
法2：我们可以将[0, i)拆解成[0, j-1)和[j, i)，由于我们已经求解了前j个字符的合法性，那么[j, i)如果也合法，那么[0, i)也合法。检查一个字符串是否出现在给定的字符串列表里一般可以用哈希表来快速判断。
代码1：动态规划（背包）
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
// 保证合法性，设置dp[0] = true
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (String word : wordDict) {
int len = word.length();
// 检查单词长度是否越界和单词是否存在字典
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
代码2：动态规划（自底向上）
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
// 字符串前i个字符可在字典中查到
dp[i] = true;
break;
}
}
}
return dp[n];
}
