子序列解题模板
子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的。
子序列问题有两种思路模板，即两种 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。
两种思路
1、 第一种思路模板是一个一维的 dp 数组：
int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = 最值(dp[i], dp[j] + ...)
}
}
比如 [最长递增子序列]，在这个思路中 dp 数组的定义是：
在子数组array[0..i]中，以 array[i] 结尾的目标子序列（最长递增子序列）的长度是dp[i]。
为啥最长递增子序列需要这种思路呢？因为这样符合归纳法，可以找到状态转移的关系。
2、 第二种思路模板是一个二维的 dp 数组：
int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (arr[i] == arr[j])
dp[i][j] = dp[i][j] + ...
else
dp[i][j] = 最值(...)
}
}
本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。
2.1 涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：
在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]。
2.2 只涉及一个字符串/数组时（比如最长回文子序列），dp 数组的含义如下：
在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]。
第一种情况可以参考：[编辑距离] 和 [最长公共子序列]。
第二种情况可以参考：[最长回文子序列]
最长递增子序列 Longest Increasing Subsequence，简写 LIS
给定一个无序的整数数组，找到其中最长上升子序列的长度
动态规划解法（O(N2)）
动态规划的核心设计思想是数学归纳法。
dp定义是这样的： dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
根据这个定义，最终结果（子序列的最大长度）应该是 dp 数组中的最大值。
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
状态转移计算dp[i]:
既然是递增子序列，只要找到前面那些结尾比 nums[i] 小的子序列，然后把 nums[i] 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。这会形成很多种新的子序列，但我们只要最长的，把最长子序列的长度作为 dp[i] 的值即可
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
完整代码如下：
int lengthOfLIS(int[] nums) {
int[] dp = new int(nums.length);
// base case
for (int i = 0; i < nums.length; i++)
dp[i] = 1;
for (int i = 0; i < nums.length; i++){
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
dp[i] = max(dp[i], dp[j]+1);
}
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
res = max(res, dp[i])
}
return res;
}
总结
首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i−1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组
最长回文子序列
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000
分析：
这个问题对 dp 数组的定义是：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
为啥这个问题要这样定义二维的 dp 数组呢？因为找状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分，这样定义容易归纳，容易发现状态转移关系。
具体来说，如果我们想求dp[i][j]，假设你知道了子问题dp[i+1][j-1]的结果（s[i+1..j-1]中最长回文子序列的长度），你是否能想办法算出dp[i][j]的值（s[i..j]中，最长回文子序列的长度）呢？
可以！这取决于s[i]和s[j]的字符：
如果它俩相等，那么它俩加上s[i+1..j-1]中的最长回文子序列就是s[i..j]的最长回文子序列。
如果它俩不相等，说明它俩不可能同时出现在s[i..j]的最长回文子序列中，那么把它俩分别加入s[i+1..j-1]中，看看哪个子串产生的回文子序列更长即可。
以上两种情况写成代码就是这样：
if (s[i] == s[j])
// 它俩一定在最长回文子序列中
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
首先明确一下 base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)。
因为i肯定小于等于j，所以对于那些i > j的位置，根本不存在什么子序列，应该初始化为 0。
另外，看看刚才写的状态转移方程，想求dp[i][j]需要知道dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]这三个位置；再看看我们确定的 base case，填入 dp 数组之后是这样：
为了保证每次计算dp[i][j]，左、下、左下三个方向的位置已经被计算出来，只能斜着遍历或者反着遍历：
我选择反着遍历，代码如下（试图写出斜着遍历技巧）：
// 反着遍历
int longestPalindromeSubseq(string s) {
int n = s.size();
// dp 数组全部初始化为 0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
dp[i][i] = 1;
// 反着遍历保证正确的状态转移
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 状态转移方程
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
// 整个 s 的最长回文子串长度
return dp[0][n - 1];
}
// 斜着遍历
int longestPalindromeSubSeq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++)
dp[i][i] = 1;
for (int k = 1; k < n; k++) {
for (int i = 0, j = k; i < n && j < n; i++, j++) {
if (s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][n-1];
}
主要还是正确定义 dp 数组的含义，遇到子序列问题，首先想到两种动态规划思路，
然后根据实际问题看看哪种思路容易找到状态转移关系。
另外，找到状态转移和 base case 之后，一定要观察 DP table，看看怎么遍历才能保证通过已计算出来的结果解决新的问题
最长公共子序列（LCS）
给你输入两个字符串s1和s2，请你找出他们俩的最长公共子序列，返回这个子序列的长度
分析：
对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划思路。先写一个dp函数：
// 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
int dp(String s1, int i, String s2, int j)
接下来只看s1[i]和s2[j]：
如果s1[i] == s2[j]，说明这个字符一定在lcs中：
如果s1[i] != s2[j]意味着，s1[i]和s2[j]中至少有一个字符不在lcs中：
由于情况三被情况一和二包含，所以可以忽略，完整代码如下
// 备忘录，消除重叠子问题
int[][] memo;
/* 主函数 */
int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 备忘录值为 -1 代表未曾计算
memo = new int[m][n];
for (int[] row : memo)
Arrays.fill(row, -1);
// 计算 s1[0..] 和 s2[0..] 的 lcs 长度
return dp(s1, 0, s2, 0);
}
// 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
int dp(String s1, int i, String s2, int j) {
// base case
if (i == s1.length() || j == s2.length()) {
return 0;
}
// 如果之前计算过，则直接返回备忘录中的答案
if (memo[i][j] != -1) {
return memo[i][j];
}
// 根据 s1[i] 和 s2[j] 的情况做选择
if (s1.charAt(i) == s2.charAt(j)) {
// s1[i] 和 s2[j] 必然在 lcs 中
memo[i][j] = 1 + dp(s1, i + 1, s2, j + 1);
} else {
// s1[i] 和 s2[j] 至少有一个不在 lcs 中
memo[i][j] = Math.max(
dp(s1, i + 1, s2, j),
dp(s1, i, s2, j + 1)
);
}
return memo[i][j];
}
上面用的是自顶向下带备忘录的动态规划思路，当然也可以使用自底向上的迭代的动态规划思路，和我们的递归思路一样，关键是如何定义dp数组，自底向上的解法如下：
int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
// 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
// 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
// base case: dp[0][..] = dp[..][0] = 0
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 现在 i 和 j 从 1 开始，所以要减一
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
自底向上的解法中dp数组定义的方式和递归解法有一点差异，而且由于数组索引从 0 开始，有索引偏移。
编辑距离
给你两个字符串 s1 和 s2，请你计算出将 s1 转换成 s2 所使用的最少操作数 。
你可以对一个字符串进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
分析:
解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。
base case 是i走完s1或j走完s2，可以直接返回另一个字符串剩下的长度。
对于每对字符s1[i]和s2[j]，可以有四种操作：
if s1[i] == s2[j]:
啥都别做（skip）
i, j 同时向前移动
else:
三选一：
插入（insert）
删除（delete）
替换（replace）
dp[i][j]的含义：
dp[i][j]
# 存储 s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
完整代码：
int minDistance(string s1, string s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
// base case，其中一个字符为空
for (int i = 1; i <= m; i++)
dp[i][0] = i;
for (int j = 1; j <= n; j++)
dp[0][j] = j;
// 自底向上求解
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1]; // 跳过
else
dp[i][j] = min(
dp[i-1][j] + 1, // 删除s[i-1]
dp[i][j-1] + 1, // 将s[i-1]插入s[j-1]
dp[i-1][j-1] + 1 // 替换
);
return dp[m][n];
}
int min(int a, int b,int c){
return Math.min(a, Math.min(b, c));
}
最大子数组和
以nums[i]为结尾的「最大子数组和」为dp[i]。
状态转移：
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
完整代码：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
// base case
// 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
注意到dp[i]仅仅和dp[i-1]的状态有关，可以进行「状态压缩」，将空间复杂度降低：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// base case
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
for (int i = 1; i < n; i++) {
// dp[i] = max(nums[i], nums[i] + dp[i-1])
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// 顺便计算最大的结果
res = Math.max(res, dp_1);
}
return res;
}