【单词拆分】
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
思路：
首先，我们依次考虑s的前i个字母能否被分割，直到i=n；
对一个确定的i，我们尝试在前i个字母中进行分割，枚举每一个分割点，如果分割点前面的部分能分割（肯定已经被计算过，直接查表即可），且分割点后的部分存在于 wordDict中，那么当前子串就是可分割的，记录到表中；
最后检查dp[n]即可。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
// dp
vector<bool> dp(n + 1, false);
dp[0] = true;
//递推
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
//bool flag=false;
// s[0]到s[j-1]能分割，s[j]到s[i-1]
if (dp[j] &&
(find(wordDict.begin(),wordDict.end(),s.substr(j, i - j)) != wordDict.end())) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};【最长递增子序列】
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路：
依次考虑前i个元素，计算以第i个元素结尾的递增子序列长度；
对第i个元素，我们检查它前面的所有元素，并试着把它接在该元素结尾的子序列后面，如果还能满足递增，则记录接上后的子序列长度；
随时记录当前找到的最大长度。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
int curMax = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
curMax = max(curMax, dp[j] + 1);
}
dp[i]=curMax;
}
return *max_element(dp.begin(),dp.end());
}
};【乘积最大子数组】
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
思路：
本题重点在于，会出现负数，想让一个包含负数的数组乘积最大，要么让这个负数乘绝对值最大的负数前缀乘积（实际值最小），要么什么也不干（如果前缀只有正数，乘正数要么不变要么变小，直接不考虑）；
再考虑正数情况，想让一个包含该数的数组乘积最大，要么让它乘上最大的正的前缀乘积，要么什么也不干（前缀积只有负数时越乘越小）；
如果遇到0，包含它的子数组乘积必为零，我们可以留到最后去判断；
以上逻辑看起来很复杂，要判断当前元素和0的关系，最大的前缀积最小的前缀积和零的关系，特殊值0的处理，等等，但实际上不管怎么样，我们需要的其实就是到当前元素为止的最大和最小乘积，而我们做的计算也只有当前元素x最大前缀积，当前元素x最小前缀积，当前元素不变三种情况，所以只要计算这三种结果，并取其中的最大值和最小值就可。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int ans = INT_MIN;
int n = nums.size();
int dpMax = 1;
int dpMin = 1;
for (int i = 0; i < n; i++) {
int temp=dpMax;
dpMax =
max(max(nums[i], nums[i] * dpMax), nums[i] * dpMin);
dpMin =
min(min(nums[i], nums[i] * temp), nums[i] * dpMin);
ans = max(ans, dpMax);
}
return ans;
}
};【分割等和自己】
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：
把题目翻译一下，其实就是能不能找出一个子数组，它的和是原数组总和的一半，这样就变成0-1背包了；
首先算一下原数组总和，如果是奇数肯定不行，如果是偶数，那么它的一半就是我们要找的子数组的和，aka背包的容量，而我们要记录的是考虑前i个物品时能否恰好把容量为j的背包装满；
依次增加当前考虑的物品数量i，倒序遍历背包容量j，首先判断当前物品i，如果它的重量正好等于当前容量j，那么可以装满，如果前i-1个物品已经能把j容量装满，那么增加一个物品没有影响，肯定也可以装满，否则考虑前i-1个物品能否装满容量j-当前重量的背包，如果能的话，加上当前物品，就正好是前i个物品装满j容量的背包；
最后，考虑到每一轮循环我们需要的信息其实都只有第i-1行，进行空间优化，用一维数组来滚动即可。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int sum=0;
for(int i=0; i<n; i++){
sum += nums[i];
}
if(sum%2 || sum<nums[n-1]) return false;
int target = sum/2;
vector<bool> dp(target+1);
dp[0]=true;
for(int i=0; i<n; i++){
for(int j=target; j>=nums[i]; j--){
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}
};【最长有效括号】
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
思路：
一开始疯狂条件判断，把自己都判晕了，后来才意识到本题的核心逻辑非常简单，归纳真有意思。
遍历串中的每个字符，我们记录以该字符结尾的最长有效子串长度；
当我们拿到一个新的字符i，有两种情况，左括号结尾的必无效，填0直接continue，右括号结尾时，我们要做的是：看看这个右括号能不能找到对应的左括号，把以字符i-1结尾的有效串包在里面，如果找到了，那么这个有效串的长度就增加了2，还没完，我们找到了最左边的括号以后，还要看看它的前一个字符能提供多长的有效串，拼接起来，此时才真正拿到了以字符i结尾的最长的有效串；
对当前字符是右括号且前一个字母是左括号的情况，我们还可以进行代码优化，直接用这两个字符组成的合法括号对拼接上前面的有效串即可（本质是用dp[i - 1]为0的信息简化了表达式）。
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
if (n == 0)
return 0;
vector<int> dp(n + 1, 0);
//dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
//左结尾必不合法
if (s[i - 1] == '(')
continue;
//右结尾时分情况讨论
else {
//正好是个左，凑一对
if (s[i - 2] == '(')
dp[i] = dp[i - 2] + 2;
//是个右，要去当前元素左边的整个合法串的左边找找有没有配对的，配上的话还要再往前接龙
else {
//配上了
if ((i - 2 - dp[i - 1] >= 0) &&
(s[i - 2 - dp[i - 1]] == '('))
dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
