动态规划
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" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
完全背包特有结构模板
class Solution {
// “数”作物品，“和”作背包
// 单词任取 → 完全背包 → 内正序
// 看作排列问题 → 内清零，外定序 → 外背包
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
//定义：dp[容量]：字符串长度为 容量 的字符串能否被拆分成字典单词组合
vector<int> dp(s.size() + 1, false);// 能取 s.size()
// 定初值：空串可以被拆分，因此dp[0]为true（意义角度：必要性）
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);
if(wordSet.find(word) != wordSet.end() && dp[j]){
// [j,i] 能拆分，且 dp[j] 可拆分时为 true
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 定义：dp[i]表示以nums[i]结尾的最长递增子序列长度
vector<int> dp(nums.size(), 1);
// 定初值：最长递增子序列的最小长度为1
int res = 1;
// 定序：从左往右，先遍历前面的元素
for(int i = 1; i < nums.size(); i++) {
for(int j = 0; j < i; j++) {
// 定式：如果nums[j] < nums[i]，则考虑将nums[i]加入到以nums[j]结尾的子序列中
if(nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
// 更新最长递增子序列长度
res = max(res, dp[i]);
}
return res;
}
};
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
维护两个dp数组是因为乘积的最大值可能同时受到正负数的影响。一个dp数组用于保存乘积的最大值，另一个dp数组用于保存乘积的最小值。乘积的最小值通常为负数，当遇到负数时，最小值可能变成最大值。所以需要同时维护两个dp数组来处理这种情况。
class Solution {
public:
int maxProduct(vector<int>& nums) {
// 定义
// dp[i]表示以第i个元素结尾的子数组的乘积的最大值
// dp_min[i]表示以第i个元素结尾的子数组的乘积的最小值
// 定式
// dp[i] = max(nums[i], dp[i-1] * nums[i], dp_min[i-1] * nums[i])
// dp_min[i] = min(nums[i], dp[i-1] * nums[i], dp_min[i-1] * nums[i])
// 定初值
// dp[0] = nums[0]
// dp_min[0] = nums[0]
// 定序
// 从左到右遍历数组
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 0); // dp数组用于保存最大乘积
vector<int> dp_min(n, 0); // dp_min数组用于保存最小乘积
dp[0] = nums[0]; // 初始值为第一个元素
dp_min[0] = nums[0]; // 初始值为第一个元素
int res = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = max(nums[i], max(dp[i-1] * nums[i], dp_min[i-1] * nums[i])); // 更新最大乘积
dp_min[i] = min(nums[i], min(dp[i-1] * nums[i], dp_min[i-1] * nums[i])); // 更新最小乘积
res = max(res, dp[i]); // 更新结果
}
return res;
}
};
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
01背包，结构固定
class Solution {
public:
// 等价 01 背包
// 背包最大容量：sum/2
// 物品 i ：nums[i]
// 物品 i 重量：nums[i]
// 物品 i 价值：nums[i]
bool canPartition(vector<int>& nums) {
// 1维 dp 解 01 背包，套路固定：
// dp 数组含义：容量为 j 时最大价值
// 遍历顺序：外物品，内背包，内倒序
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 100
// 和最大为 20000， 故 dp 长度取 20000/2+1，即 10001
// 0 下标表示容量为 0，此时价值也为 0，故取 0
// 带覆盖 → 非 0 下标初始值保证取最值正常进行即可，故取 0
// 故所有下标均初始化为 0
vector<int> dp(10001, 0);
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
}
if(sum % 2 == 1) return false; //必不可能由两个整数等分
int bagMax = sum / 2;
for(int i = 0; i < nums.size(); i++){
for(int j = bagMax; j >= nums[i]; j--){
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[bagMax] == bagMax) return true;
return false;
}
};
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
class Solution {
public:
int longestValidParentheses(string s) {
// 定义：dp[i]表示以索引i结尾的最长有效括号的长度
// 定初值：索引为 0 时，最长有效括号长度为 0
vector<int> dp(s.length(), 0);
int maxLen = 0;
// 定序：从左向右遍历字符串
for (int i = 1; i < s.length(); i++) {
//只有在')'字符之前才可能有有效括号
if (s[i] == ')') {
// 定式：如果s[i-1]是'('，那么dp[i]=2+dp[i-2]，否则dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]
if (s[i - 1] == '(') {
// 当前字符为')'，前一个字符为'('，形成了一对有效括号
// 更新dp[i]为dp[i-2]+2
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
// 当前字符为')'，前一个字符为')'
// 如果前一个字符的最长有效括号长度大于0，并且前一个字符的前面一个字符为'('
// 则可以与之匹配，形成更长的有效括号
// 更新dp[i]为dp[i-1]+2+dp[i-dp[i-1]-2]
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
// 更新最大长度
maxLen = max(maxLen, dp[i]);
}
}
// 返回最长有效括号的长度
return maxLen;
}
};