62. 不同路径
Note: 本题除动态规划外，还可以使用组合数学方法，因为从起点到终点，无论如何需要n+m-2步，并且其中m-1步一定是向下，问题转化为从n+m-2个数中取m-1个数，因此最终的答案是 ，为了计算这个组合数，我们考虑计算组合数 的一般方法：
因此我们可以通过如下方法来计算：
long long ans = 1;
int numerator = p - q + 1, denominator = 1;
while (denominator <= q) {
ans = ans * numerator++ / denominator++;
}
return ans;
为什么这里我们不用怕除法会导致取整，进而产生错误结果呢，因为这里的除法是一定能整除的，假设当前计算到第k步（k ≤ q），那么此时的ans是：
这也是个组合数，很明显它是个整数，这意味着，每一步除法其结果都必然为整数。因此不需要怕除不尽取整导致错误结果。本题中p = m+n-2, q = m-1, p-q+1 = n，因此最终代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
// 组合数学方法，从m+n-2步中选择m-1步向下
long long ans = 1;
int numerator = n, denominator = 1;
while (denominator <= m - 1) {
ans = ans * numerator++ / denominator++;
}
return ans;
}
};
343. 整数拆分
Note: 这里注意dp[i]表示数字i拆分得到的最大乘积（i≥2时才有意义），故初始化条件为dp[2]=1，而遍历从i=3开始。另外在内层循环中，j=1和j=i-1意义相同，故终止条件设置为j<i-1以减少一次重复计算（累计n次）。
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n; ++i) {
for (int j = 1; j < i - 1; ++j) {
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
};
Note: 本题还可以用数学解法，运用算术几何平均值不等式可以证明：将整数分为多个3的时候拆分乘积最大，故可用快速幂将时间复杂度降低到O(logn)。
96. 不同的二叉搜索树
Note: 本题也可以用记忆化搜索，但是由于实际需要考虑1-n之间每个数i对应的dp[i]，所以dp[1-n]均要计算出来，因此复杂度和dp无异。
46. 携带研究材料（第六期模拟笔试）
Note: 0-1背包原题
416. 分割等和子集
Note: 背包问题的应用，把背包容量设置为1 - sum/2，每次往里面放一个数，或者不放，看最后容量为sum/2的背包是否恰好放满。另，可用bitset来压缩状态。
1049. 最后一块石头的重量 II
Note: 同416. 分割等和子集。由于最终剩下的石头（若没剩下则视为剩下一个重量为0的石头）一定可以表示为 ，那么我们取所有组合里使得上述和非负且最小的组合，即得到我们要找的最后一块石头的最小重量，考虑将此组合中为1的石头分到同一堆，而为-1的石头分到另一堆，那么问题转化为求两堆石头总重量的差值的最小值，显然，这是将所有石头分为两堆，然后两堆总重量越接近越好，假设两堆中重量总和小的一堆重量为m，则最终答案为sum - m - m = sum - 2 * m。因此，m越大越好。那么采用上题思路，看看最后容量为sum/2的背包中装的石头重量为多少（dp[sum/2]），这就是我们要求的m，因为这是重量总和小的那一堆石头（也就是重量小于sum/2的一堆）的最大重量。本题同样可以用bitset来优化。
494. 目标和
Note: 本题和前两题的主要区别在于递推公式需要修改，因为前两题的dp数组中dp[j]都代表容量为j的背包能装的最大重量，原因是我们需要通过知道这样的最大重量来确定答案（比如容量为sum/2的背包是否能装满，或者其最大装的重量是多少），但是本题是要求装满某个容量的可能组合的总数，那么显然dp[j]的意义应该修改为：能装满容量为j的背包的组合数，或者在本题意义下，是和为j的组合总数，那么递推公式也很显然：dp[j] = dp[j] + dp[j - nums[i]]，因为在判断每个数是否在组合中时，它要么在，要么不在，如果不在，那么有dp[j]中可能，因为在放完上一个数时，就有dp[j]个组合使得组合总和为j，而本次的组合总和未发生变化（本次数没放进组合）；如果放进了，则在放完上一个数时，组合总和需要为j - nums[i]（nums[i]为本次放入的数字），这意味着，本次数放完后组合总和为j的可能组合数有dp[j - nums[i]]个，将这二者加和即可。本题思路实际可以用于求解组合总和为sum的组合数量。另外注意这里初始化时，dp[0]为1，因为在放所有数字之前，很明显组合总和就是0，所以组合总和为0有1种情况，而其他dp[j]都为0。本题不能用bitset优化，因为bitset只能记录过程中某个组合总和的存在性，而无法记录数量。
474. 一和零
Note: 二维背包，没什么好说的，注意本题求满足要求的组合内最大元素个数，因此dp[j][k]表示容量为j个0和k个1的情况下背包内元素最大个数，递推公式为dp[j][k] = max(dp[j][k], dp[j - zero][k - one] + 1)
52. 携带研究材料（第七期模拟笔试）
Note: 完全背包原题，与0-1背包唯一不同在于遍历顺序，在一维数组的前提下，0-1背包必须对背包容量倒序遍历，否则同一个物品可能放入多次，违反0-1背包限制，同样背包容量遍历必须放在内层，否则计算dp[j]所需的左侧dp[j-weights[i]]还未计算，会导致每个背包最多只放进了一个物品；完全背包则不同，首先每个物品可以放入多次，因此需要正序遍历（是必须！否则每个物品最多放入一次，变成0-1背包），另外物品与背包遍历顺序谁先谁后无所谓，因为计算dp[j]所需的左侧dp[j-weights[i]]总是已经计算过了。（可以理解为每一列是一个0-1背包，然后在列从左向右计算的过程是在0-1背包上累加0-1背包，以达到完全背包的效果，而如果是从右向左计算，是没有累加的，因为左边还未计算，所以相当于每一列最多放了一个，则所有背包都最多只有一个物品）。当然内外层遍历顺序对于具体题目，有不同的表现。
518. 零钱兑换 II
Note: 注意本题不能颠倒两个for的顺序，因为要求总和达到目标和的组合总数，而组合关心前后顺序，即不可以向前看，因此必须物品（硬币编号）遍历在外，否则会出现组合重复的情况，如{1,5}和{5,1}。（这一情况计算出的总数是排列数）。因此对于目标和总数，如果是求组合数那就是物品遍历在外层，求排列数则是背包遍历在外层。
377. 组合总和 Ⅳ
Note: 上面说的求排列个数的情况，注意背包遍历在外层以及处理中间结果溢出。
57. 爬楼梯（第八期模拟笔试）
Note: 卡码网的57题相比于70. 爬楼梯，更类似于背包问题。对问题进行转化，就相当于你有物品价值[1, 2, ..., m] （m为一次最多能爬的楼梯数），每个物品有无限个（相当于同一楼梯数可以爬无限次），求物品价值总和为n的所有排列个数，那么该问题就是一个完全背包求排列问题，背包容量外层循环，物品价值内层循环。
322. 零钱兑换
Note: 求的是每个组合内元素的最少个数，而非组合总数，因此和组合总数排列（物品遍历必须在外层）/组合（背包遍历必须在外层）问题不同，循环内外层顺序无关紧要，并且递推公式也是经典背包问题的递推（最小值/最大值），这里主要注意一下初始化，除了dp[0]以外其他dp[j]均初始化为INT_MAX，代表找不到总和满足要求的组合。在递推过程中，只有当dp[j-coins[i]]不为INT_MAX时，才去取最小值，否则导致溢出：
for (int i = 0; i < n; ++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);
}
}
279. 完全平方数
Note: 本题和322.零钱兑换几乎相同，连初始化条件都相差无异，主要区别在于这里的物品是从1到n之间所有的完全平方数[1, 4, 9, ...]，另外有个细微的区别在于这里不需要判断溢出，因为对于每个自然数n，其总是可以分解成n个1的和，也就是总是可拆分的（至多拆成n个完全平方数），与上一题不同，上一题由于硬币金额是随机值，不一定正好可拆分，INT_MAX会在计算过程中保留，而本题不会。
139. 单词拆分
Note: 本题主要难在dp数组的意义以及递推公式，对于这类true/false的问题，dp数组需要为bool类型，比如本题中dp[j]需要代表s[0:j]是否可以拆分成wordDict里的单词组合（准确来说是排列）。首先将单词看作物品，将s结束位置看作背包，由于是完全背包排列，那么背包遍历必须在外层，而递推公式如下：
int size = wordDict[i].size();
dp[j] = dp[j - size] && !s.compare(j - size, size, wordDict[i]);
因为对于内层循环中的任一个单词，计算减去这个单词长度size的结束位置j - size，先看dp[j-size]是否为真，即s[0:j-size]可以由单词表里单词组成，然后再看s[j-size:j]这个子串是否等于当前判断的单词（均左闭右开），如果均为真，那么显然s[0:j]就可以由单词表内单词组成。对于给定的（外层）j，只要内层循环中的任一单词可以使得dp[j]为真，那么直接break，说明该位置能够被满足，如此递推j，最后判断dp[s.size()]是否为真，初始化时，只设dp[0]为true，可理解为s[0:0]总可被单词表内单词组成（就好像单词表中有一空单词一样）。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size(), wordNum = wordDict.size();
vector<bool> dp(n + 1, 0);
dp[0] = true;
// 以单词列表作为物品，结束位置作为背包
for (int j = 1; j <= n; ++j) {
for (int i = 0; i < wordNum; ++i) {
int size = wordDict[i].size();
// 使用compare函数避免拷贝带来的性能损耗
if (j >= size) dp[j] = dp[j - size] && !s.compare(j - size, size, wordDict[i]);
if (dp[j]) break;
}
}
return dp[n];
}
};
另外这里在比较当前单词与子串时，采用了compare函数，该函数传入待比较字符串的const 引用，因此避免了substr直接比较造成的额外性能损耗。
56. 携带矿石资源（第八期模拟笔试）
Note: 多重背包原题，基本与0-1背包无异，但需要加一个内层循环，来表示每种物品的数量。面试不会考
198. 打家劫舍
Note: 经典打家劫舍系列的第一题。
213. 打家劫舍 II
Note: 和上一题唯一区别在于首尾不能都抢，因此考虑两种情况：抢头不抢尾，抢尾不抢头，然后取更大值即可。
337. 打家劫舍 III
Note: 打家劫舍终极版，树形DP入门，将整个树作为一个dp数组，每个节点把自己以及孩子的信息都上报。
121. 买卖股票的最佳时机
Note: 贪心和dp均可，由于本题较为简单，贪心比dp合适。
122. 买卖股票的最佳时机 II
Note: 也较为简单，直接使用贪心更合适。相比于I来说可以买卖多次。
123. 买卖股票的最佳时机 III
Note: 相比于121.买卖股票的最佳时机，主要区别在于可以买两次，那么需要额外的两个状态（第二次购入 和 第二次卖出）。
188. 买卖股票的最佳时机 IV
Note: 上一题的升级版，如果最多可以买卖k次，那么就设置2*k个状态。
309. 买卖股票的最佳时机含冷冻期
Note: 122. 买卖股票的最佳时机 II的升级版，将原有的持有股票和未持有股票状态扩展为4个：持有股票，当天卖出, 冷冻期, 以及保持未持有（非冷冻期）状态，状态转移如下图：
根据该状态转移图来得到递推方程。
714. 买卖股票的最佳时机含手续费
Note: 和买卖股票II唯一的区别在于多了一个手续费。
300. 最长递增子序列
Note: 本题朴素方法是用dp[j]来记录以下标j结尾的最长递增子序列的长度，然后遍历第0到j-1个数来找出所有比第j个数小的数i，并让dp[j]取得最大的dp[i]+1。高级方法可以用贪心+二分搜索来优化到O(nlogn)。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// dp方法
// int n = nums.size(), ans = 1;
// vector<int> dp(n, 1);
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < i; ++j) {
// if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
// }
// ans = max(ans, dp[i]);
// }
// return ans;
// 贪心+二分搜索
int n = nums.size(), len = 1;
int *d = new int[n + 1];
d[1] = nums[0];
for (const int& num: nums) {
if (d[len] < num) {
d[++len] = num;
} else {
int l = 1, r = len, pos = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
if (d[mid] < num) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = num;
}
}
return len;
}
};
1143. 最长公共子序列
Note: 注意以上题目压缩dp数组时的操作，对于LIS（最长递增子序列）系列问题，一维dp可被压缩为0维，对于LCS（最长公共子序列）系列问题，二维dp可被压缩为1维，但是注意避免覆盖。对于LIS系列，必须倒序遍历，而对于LCS问题，由于dp[i][j]同时依赖于左上和左两个位置，因此无法通过单纯的改变遍历顺序来压缩，因此有两个trick：使用两行一维数组来回滚动，或者使用pre来记录上一行的左上。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(2, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i % 2][j] = dp[(i + 1) % 2][j - 1] + 1;
} else {
dp[i % 2][j] = max(dp[(i + 1) % 2][j], dp[i % 2][j - 1]);
}
}
}
return dp[m % 2][n];
}
};
1035. 不相交的线
Note: 上一题的低级换皮（笑）
53. 最大子数组和
Note: 本题除了贪心（本质上是dp），还有线段树做法：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 线段树
return get(nums, 0, nums.size() - 1).mSum;
}
// 线段树状态
struct Status {
int lSum, rSum, mSum, iSum;
};
// 合并两个线段
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status){lSum, rSum, mSum, iSum};
}
// 分治
Status get(vector<int>& a, int l, int r) {
if (l == r) return (Status){a[l], a[l], a[l], a[l]};
int m = l + (r - l) / 2;
Status left = get(a, l, m);
Status right = get(a, m + 1, r);
return pushUp(left, right);
}
};
392. 判断子序列
Note: 本题有三种解法，第一种最简单高效的双指针；第二种是预处理主串t，用dp[i][j]来表示t中从第i个字符起，字符j第一次出现的位置，如果t[i] == j那么dp[i][j] = i，否则dp[i][j]等效于dp[i+1][j]，遍历时从后往前，初始化时设置全部dp[t.size()][j]为t.size()。在检查s时，从下标idx=0起，根据dp数组寻找字符s[idx]在t中出现的第一个位置，并跳转到该位置的下一个位置进行下一次检查，一旦跳转到t.size()位置，说明t中往后找不到这样的字符了，检查失败。这样做的好处是，只要处理了一次字符串t，之后的s都可以快速处理（有点类似KMP），可以应对大量s的场景。 第三种则同最长公共子序列，判断s和t的最长公共子序列是否等于s的长度，只是递推公式在字符不匹配时，只能从t中删，而不能从s中删，也就是当s[i] != t[j]是，只能dp[i][j] = dp[i][j - 1]。
class Solution {
public:
bool isSubsequence(string s, string t) {
// 方法一：双指针
int i = 0, j = 0;
for (;i < s.size() && j < t.size();j++) {
if (s[i] == t[j]) i++;
}
if (i == s.size()) return true;
return false;
// 方法二：预处理t的做法
vector<vector<int>> dp(t.size() + 1, vector<int>(26, 0));
int t_size = t.size();
int i, j;
for (i = 0;i < 26;i++) {
dp[t_size][i] = t_size;
}
for (i = t.size() - 1;i >= 0;i--) {
for (j = 0;j < 26;j++) {
if (t[i] - 'a' == j) dp[i][j] = i;
else dp[i][j] = dp[i + 1][j];
}
}
int next = 0;
for (i = 0;i < s.size();i++) {
if (dp[next][s[i] - 'a'] == t_size) return false;
next = dp[next][s[i] - 'a'] + 1;
}
return true;
// 方法三：最长公共子序列（空间优化）
int m = s.size(), n = t.size();
vector<vector<int>> dp(2, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i % 2][j] = dp[(i + 1) % 2][j - 1] + 1;
} else {
dp[i % 2][j] = dp[i % 2][j - 1];
}
}
}
return dp[m % 2][n] == m;
}
};
115. 不同的子序列
Note: 设置dp[i][j]表示s[0:i - 1]的子序列中出现t[0:j - 1]的次数：
- 如果
s[i - 1]和t[j - 1]相等，显然dp[i][j]可分为两部分，一部分等效于s[0:i - 2]的子序列中出现t[0:j - 2]的次数，也就是dp[i - 1][j - 1]，另一部分等效于s[0:i - 2]的子序列中出现t[0:j - 1]的次数，也就是dp[i - 1][j]。(举个例子，bag和ba，各自加了一个g以后，变成bagg和bag，这里除了原来匹配的1次0b 1a 3g和0b 1a 2g，还多了一个0b 1a 2g和0b 1a 2g，这一部分就是dp[i - 1][j]，而且由于这里是在s子序列中找完整的t，故t不能删，只能删s，所以dp[i][j]只由这两部分构成，而不能包括dp[i][j - 1]，这相当于删了t[j - 1])； - 如果不相等，则
dp[i][j]只可能由上述的第二部分构成，即dp[i][j] = dp[i - 1][j]，相当于必须删s[i - 1]来获得匹配！比如bag和ba，前者添加c，后者添加g，变为bagc和bag，此时的dp[i][j]就来自于dp[i - 1][j]。
至于初始化，dp[i][0]很明显全为1，dp[0][j](j > 0)很明显全为0。经过空间优化的代码如下：
class Solution {
public:
int numDistinct(string s, string t) {
int slen = s.size(), tlen = t.size();
vector<unsigned long long> dp(tlen + 1, 0);
dp[0] = 1;
for (int i = 1; i <= slen; ++i) {
for (int j = min(tlen, i); j >= 1; --j) {
if (s[i - 1] == t[j - 1])
// 这里右边的dp[j]实际上是dp[i-1][j]，dp[j-1]实际上是dp[i-1][j-1]
dp[j] += dp[j - 1];
}
}
return dp[tlen] % (unsigned long long)(pow(10, 9) + 7);
}
};
583. 两个字符串的删除操作
Note: 本题两个字符串均可删除，因此不同于之前题目中模式串不可删除的情况。用dp[i][j]来表示对word1[0:i - 1]和word2[0:j - 1]进行删除处理，使它们相等所做的最小操作次数。那么类似于之前的分析，考虑word1[i - 1]和word2[j - 1]是否相等的情况：
-
若相等，那么要使得
word1[0:i - 1]和word2[0:j - 1]相等，只需要让word1[0:i - 2]和word2[0:j - 2]相等，两个末尾字符根本不用操作，这便是最小操作次数。 -
若不相等，那么要使得
word1[0:i - 1]和word2[0:j - 1]相等，有三种操作：①. 删
word1[0:i - 1]，让word1[0:i - 2]和word2[0:j - 1]相等，即dp[i - 1][j]；
②. 删word2[0:j - 1]，让word1[0:i - 1]和word2[0:j - 2]相等，即dp[i][j - 1]；
③. 删word1[0:i - 1]和word2[0:j - 1]，让word1[0:i - 2]和word2[0:j - 2]相等，即dp[i - 1][j - 1]；但是这种情况已经蕴含在前两种情况中，删两个末尾字符，和先删一个末尾字符，再在后续操作中再删除一个是等效的，没有什么区别（至少本情况最小操作次数一定大于等于前两种）。那么
dp[i][j]应该取情况①和②的最小值，即min(dp[i - 1][j], dp[i][j - 1])。
对于初始化，显然dp[0][j] = j, dp[i][0] = i。状态压缩后代码如下（仍使用奇偶滚动数组）：
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size(), len2 = word2.size();
vector<vector<int>> dp(2, vector<int>(len2 + 1, 0));
for (int j = 0; j <= len2; ++j) dp[0][j] = j;
for (int i = 1; i <= len1; ++i) {
dp[i % 2][0] = i;
for (int j = 1; j <= len2; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i % 2][j] = dp[(i + 1) % 2][j - 1];
} else {
dp[i % 2][j] = min(dp[(i + 1) % 2][j] + 1, dp[i % 2][j - 1] + 1);
}
}
}
return dp[len1 % 2][len2];
}
};
72. 编辑距离
Note: 分析过程和之前类似，但是在两子串末尾不相等的情况下，让word1[0:i-1]变为word2[0:j-1]的最小操作次数dp[i][j]，有三种情况：
- 将
word1[0:i-1]变为word2[0:j-2]，并在末尾增添word2[j-1]，即dp[i][j-1]+1； - 删去
word1[i-1]，将word1[0:i-2]变为word2[0:j-1]，即dp[i-1][j]+1； - 将
word1[0:i-2]变为word2[0:j-2]，并将word1[i-1]修改为word2[j-1]，即dp[i-1][j-1]+1；
此时dp[i][j]取这三者之间的最小值，不同于上题中有一种情况被其他两种涵盖，这三种操作分别对应题目中的增，删和改。
使用prev保留dp[i-1][j-1]来优化空间，代码如下：
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size(), len2 = word2.size();
vector<int> dp(len2 + 1, 0);
for (int j = 0; j <= len2; ++j) dp[j] = j;
int prev, tmp;
for (int i = 1; i <= len1; ++i) {
dp[0] = i;
// 每一层初始的prev，是相对于(i, 1)的dp[i-1][j-1]，即dp[i-1][0],也就等于i-1
prev = i - 1;
for (int j = 1; j <= len2; ++j) {
// temp保留的是本行dp[j]处理之前的dp[j]，在本次dp[j]处理完成之后赋给prev,
// prev对于本行下一个j来说是dp[i-1][j-1]
tmp = dp[j];
if (word1[i - 1] == word2[j - 1]) {
dp[j] = prev;
} else {
dp[j] = min(dp[j], min(dp[j - 1], prev)) + 1;
}
prev = tmp;
}
}
return dp[len2];
}
};
647. 回文子串
Note: 可以用动态规划做，dp[i][j]表示s[i:j]是否是回文串（bool类型）。当然动态规划占用空间较大，因此使用双指针中心扩展法更优，代码如下：
class Solution {
public:
int countSubstrings(string s) {
// 动态规划
int n = s.size(), ans = 0;
vector<vector<bool>> dp(n, vector<bool>(n, 0));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j]) {
if ((j - i <= 1) || (dp[i + 1][j - 1])) {
dp[i][j] = true;
++ans;
}
}
}
}
return ans;
// 中心扩展
int result = 0, n = s.size();
for (int i = 0; i < n; ++i) {
result += extend(s, i, i, n);
result += extend(s, i, i + 1, n);
}
return result;
}
// 中心扩展
int extend(string&s, int l, int r, int n) {
int result = 0;
while (l >= 0 && r < n && s[l] == s[r]) {
++result;
--l;
++r;
}
return result;
}
};
当然，最优的算法是马拉车算法，以后有时间再学习（逃）。
516. 最长回文子序列
Note: 本题与回文子串主要不同在于不一定连续，故设dp[i][j]表示s[i:j]内回文子序列的最大长度，如果s[i]和s[j]相等，那么s[i:j]里的最长回文子序列显然可以由s[i+1:j-1]的最长回文子序列向左右各扩展一步得到，因此dp[i][j] = dp[i+1][j-1] + 2。否则我们没有必要同时考虑s[i]和s[j]，因为它们无法使得s[i+1:j-1]内的最长回文子序列得到扩展，那么只考虑一头，就是dp[i+1][j]（只考虑s[j]）和dp[i][j-1]（只考虑s[i]），二者取最大，因此dp[i][j] = max(dp[i+1][j], dp[i][j-1])。本题和上一题都要注意，外层遍历倒序，内层遍历正序，因为外层i需要i+1比i先计算，内层j需要j-1比j先计算（dp[i][j]依赖于dp[i+1][j-1]）。
10. 正则表达式匹配
Note: 很好的一道题，类似于最长公共子序列系列，需要二维dp数组来记录两个字符串每一个位置是否匹配。这里设dp[i][j]表示s[0:i - 1]和p[0:j - 1]是否匹配，设isMatch(i, j)表示s[i - 1] == p[j - 1] || p[j - 1] == '.'，很明显这说明两字符串的当前位置是匹配的，那么如果isMatch(i,j)为真，则dp[i][j] = dp[i - 1][j - 1]，否则就需要分情况讨论：
如果p[j - 1] == '*'，那么应该先检查s[i - 1]和p[j - 2]是否匹配（这里由于p是合法的，因此j - 1 ≥ 1，j必然大于等于2），也就是isMatch(i, j - 1)是否为真。如果不匹配，那么很明显s[i - 1]不能由p[j - 2]和一个*号扩展而来（如a和b*），则必须看s[0:i - 1]和p[0:j - 3]是否匹配，也就是dp[i][j] = dp[i][j - 2]；
如果匹配，则p[j - 1]处的*号可能对p[j - 2]处的字符（也就是s[i - 1]）匹配零次或多次，如果匹配零次，那么p[j - 2]和p[j - 1]将被忽略，同样有dp[i][j] = dp[i][j - 2]；如果匹配多次，转换思路，也就是至少匹配一次，那么就看s[0:i - 2]和p[0:j - 1]是否匹配，比如aa和a*，因为至少匹配的一次 ，也就是s[i - 1]我们不考虑在内，也就是dp[i][j] = dp[i - 1][j]，只要这两情况有一个为真，dp[i][j]就为真，否则为假，因此dp[i][j] = dp[i][j - 2] | dp[i - 1][j]。
如果p[j - 1] != '*'，因为p[j - 1]也不是.，那么它就是一个普通字符，而且p[j - 1] != s[i - 1]，此时显然s[0:i - 1]和p[0:j - 1]是不匹配的，因此dp[i][j] = false。
此外还要注意的是初始化条件，很明显dp[0][0]为true（想象s和p是两个空字符串，它们显然匹配），而其他dp[i][0]都是false，因为只要p为空，而s不为空，很明显它们是不匹配的。而dp[0][j] (j > 0)的初始化就更复杂一些，不能简单判断，如果p[j - 1]不为*，那么p[0:j - 1]至少要匹配一个字符，对于空字符串s很明显不匹配，那么此时dp[0][j]应为false；反之，p[j - 1]为*，那么p[j - 1]可能使得p[j - 2]匹配零次，此时dp[0][j] = dp[0][j - 2]（前面已经讨论过）。
class Solution {
public:
bool isMatch(string s, string p) {
int sn = s.size(), pn = p.size();
vector<vector<bool>> dp(sn + 1, vector<bool> (pn + 1, false));
dp[0][0] = true;
function <bool(int, int)> isMatch = [&](int i, int j) {
return s[i - 1] == p[j - 1] || p[j - 1] == '.';
};
for (int j = 1; j <= pn; ++j) {
if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
else dp[0][j] = false;
}
for (int i = 1; i <= sn; ++i) {
for (int j = 1; j <= pn; ++j) {
if (isMatch(i, j)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
if (p[j - 1] == '*') {
if (isMatch(i, j - 1)) dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
else dp[i][j] = dp[i][j - 2];
} else {
dp[i][j] = false;
}
}
}
}
return dp[sn][pn];
}
};
32. 最长有效括号
Note: 经典字符串类题目，基本只要看到字符串 最长 最短 匹配的字眼，就可以考虑动态规划。
本题求最长有效括号，那么用dp[i]来表示以s[i - 1]结尾的最长有效括号串长度，那么如果s[i - 1]是(，很明显dp[i]为0；
如果为右括号，主要就是看前一个字符s[i - 2]是否是(，如果是那么s[i - 2]和s[i - 1]就凑了一对有效括号，看s[i - 3]结尾的最长有效括号串多长，因此dp[i] = dp[i - 2] + 2；
但如果s[i - 2]是)，那么就得看以s[i - 2]结尾的最长有效括号串多长，这里是dp[i - 1]，因此我们检查i - 2 - dp[i - 1]这个位置，这个位置是 以s[i - 2]结尾的最长有效括号串 的前一个字符，如果这个位置有字符，并且他是(，那么以s[i - 1]结尾的最长有效括号串其长度至少是以s[i - 2]结尾的最长有效括号串（这个括号串以s[i - 1 - dp[i - 1]]为起点，以s[i - 2]为终点，长度为dp[i - 1]）的长度+2（加上最外面一对括号s[i - 2 - dp[i - 1]]和s[i - 1]，长度就是dp[i - 1] + 2)。而除了这个之外，还要算上以s[i - 3 - dp[i - 1]]结尾的最长有效括号串，因为如果s[i - 1]使得s[i - 2 - dp[i - 1] : i - 1]连成了一个新的最长有效括号串，它很有可能还会连上前面以s[i - 3 - dp[i - 1]]结尾的最长有效括号串，因此dp[i]还要加上这一段的长度，所以此时dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]；
但如果i - 2 - dp[i - 1]这个位置是不合法的（<0）或者此位置字符不为(，那么也不用继续判断了，此时dp[i]就是0，因为s[i - 1]处的)在上一个最长有效括号串（也就是dp[i - 1 - dp[i - 1]到dp[i - 2]的一段）的前一个位置找不到匹配的括号。为什么这就能判断呢？因为此时s[i - 1]和s[i - 2]都是)，能和s[i - 2]匹配的括号一定是s[i - 1 - dp[i - 1]]，那么能和s[i - 1]匹配的括号一定是s[i - 2 - dp[i - 1]]。
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int* dp = new int[n + 1];
memset(dp, 0, (n + 1) * sizeof(int));
int ans = 0;
for (int i = 2; i <= n; ++i) {
if (s[i - 1] == ')') {
if (s[i - 2] == '(') {
dp[i] = dp[i - 2] + 2;
ans = max(ans, dp[i]);
}
else if (i - 2 >= dp[i - 1] && s[i - 2 - dp[i - 1]] == '(') {
// dp[i] = dp[i - 1] + 2 + ((i - 3 - dp[i - 1] >= 0) ? dp[i - 2 - dp[i - 1]] : 0);
dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];
ans = max(ans, dp[i]);
}
}
}
return ans;
}
};