DP笔记(5)：双串线性DP问题，从回文字串到子序列问题模板
Author：zhoulujun Date：
本文从「最长公共子序列问题」展开，总结四道子序列问题
最长回文字串
回文串是面试常常遇到的问题（虽然问题本身没啥意义），之在《双指针：对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等)》里面的最长回文子串，用分离双指针解决。虽然用双指针与动态规划，时间复杂度都为O(n^2)，而双指针空间复杂度更低。那为什么还有要探讨动态规划求解？因为，
动态规划方法在直观性、可扩展性、可调试性等方面有独特的优势（更具有普适性！）
直观性和可扩展性：通过构建一个二维表格（DP表）记录所有可能子串的回文性质，提供了一个直观的思路来理解和解决问题。
可捕捉所有子问题的解：动态规划方法计算并存储所有子串的解，保证每一个子问题都被解决。
灵活性和可调试性：可以很方便地调试和查看中间结果。这在复杂的字符串操作中非常有用，有助于理解和验证算法的正确性。
统一处理不同长度子串：动态规划方法可以在一次遍历中处理所有长度的子串，而不需要区分奇数长度和偶数长度的子串。
动态规划的方法，之前讲过 《DP笔记(2)：线性DP之单线性，爬楼梯、打家劫舍、2键/4键键盘》，
但本篇使用一个一维数组（单线性） DP ，推导中整个脑壳都是嗡嗡的！
具体参看《最长回文子串问题（五种方法）》
二维动态规划方法
相比 一维动态规划方法 而言， 二维数组上的动态规划方法的思路更直白。
回文串两边加上两个相同字符，会形成一个新的回文串 。
方法是，建立二维数组 dp ，找出所有的回文子串。dp[i][j] 记录子串 i..j 是否为回文串 。
首先，单个字符就形成一个回文串，所以，所有 dp[i][i] = true 。
然后，容易得到递推关系：如果字符 s[i] 和 s[j] 相等，并且子串 i+1..j-1 是回文串的话，子串 i..j 也是回文串。也就是，
如果 s[i] == s[j] 且 dp[i+1][j-1] = true 时，dp[i][j] = true 。
这是本方法中主要的递推关系。
不过仍要注意边界情况，即 子串 i+1..j-1 的有效性 ，当 i+1 <= j-1 时，它才有效。
反之，如果不满足，此时 j <= i+1 ，也就是子串 i..j 最多有两个字符， 如果两个字符 s[i] 和 s[j] 相等，那么是回文串。
最后，考虑到 主要的递推关系 是由已知子串 i+1..j-1 的情况， 递推到 i..j 的情况， 因此，迭代过程需要反序迭代变量 i ，正序迭代 j 。
代码
function LongestPalindromicSubstring(s) { // 返回给定字符串 s 的最长回文子串的长度
const n = s.length;
if (n <= 0) return 0;
const dp = Array.from({ length: n }, () => Array(n).fill(false));// dp[i][j] 表示 s[i..j] 是否回文，j >= i
for (let i = 0; i < n; i++) {// 初始化，这一段可以忽略
for (let j = i; j < n; j++) {
dp[i][j] = false;
}
}
for (let i = 0; i < n; i++) dp[i][i] = true;// 单个字符 s[i..i] 构成回文（将对角线（即i==j的情况）赋值为true）
let max_length = 1; // 记录最大回文子串的长度，至少为 1
// 考虑递推,主要的递推关系是 dp[i][j] = dp[i+1][j-1],所以倒序遍历 i ，才可以形成递推
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j]) {
if (j - 1 >= i + 1) { // 子串 s[i+1..j-1] 有效性
if (dp[i + 1][j - 1]) dp[i][j] = true;
} else { // 此时 j < i + 2 即 j <= i+1
dp[i][j] = true; // 再之 s[i] == s[j]，必回文
}
}
if (dp[i][j]) {
const length = j - i + 1; // 更新最大长度
if (length > max_length) max_length = length;
}
}
}
return max_length;
}不过上面的代码与标准动态规划看起来还是感觉有些偏差（不对味），还是动态五部曲来来推导
最长回文字符串动态五部曲解题
确定dp数组（dp table）以及下标的含义
dp[i][j] 表示子串 s[i..j] 是否为回文串。
确定递推公式：
当 i == j 时，s[i..j] 只有一个字符，因此 dp[i][j] = True。
当 j == i + 1 时，即子串 s[i..j] 只有两个字符。若这两个字符相同，则 dp[i][j] = True。
对于长度大于2的子串，s[i..j] 是回文的条件是 s[i] == s[j] 且 s[i+1..j-1] 也是回文串，即 dp[i+1][j-1] = True。因此递推公式为：
我们可以将所有情况综合起来，给出一个统一的递推公式：
初始化数组
dp数组初始化为 false，表示子串 s[i..j] 还未判断是否为回文。
dp数组对角线都为true(i===j时)，即单个字符的子串都是回文串
最终代码
function longestPalindrome(s) {
const n = s.length;
if (n <= 0) return 0;
const dp = Array.from({ length: n }, () => Array(n).fill(false)); // 初始化 dp 数组
let maxLength = 1; // 记录最大回文子串的长度，至少为 1
let start = 0; // 记录最大回文子串的起始位置
for (let i = 0; i < n; i++) { // 单个字符 s[i..i] 构成回文（将对角线赋值为 true）
dp[i][i] = true;
}
for (let i = 0; i < n - 1; i++) { // 两个字符的情况
if (s[i] === s[i + 1]) {// 当 j == i + 1 时,若这两个字符相同,则为回文。如aa bb cc
dp[i][i + 1] = true;
start = i;
maxLength = 2;
}
}
for (let length = 3; length <= n; length++) { //考虑长度大于 2 的子串，子串长度从 3 开始
for (let i = 0; i <= n - length; i++) {
const j = i + length - 1; // 计算子串的结束位置
if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i;
maxLength = length;
// palindromes.push(s.slice(i, j + 1)); // 记录回文子串 ，注意单个 与双个字符串不要漏掉
}
}
}
return maxLength;
// return s.substring(start, start + maxLength);// 返回最长回文字符串
}上面的代码可以作为模板，解决最长回文字符串一系列问题。
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
示例 1：输入：nums = [10,9,2,5,3,7,101,18] 输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
最长递增子序列有一个性质： 最长递增子序列的尾巴元素一定是这个序列中最大的元素 。
因为此题是单行线动态规划，之前详细讲过《DP笔记(2)：线性DP之单线性，爬楼梯、打家劫舍、2键/4键键盘》，所以不细讲此题了。
动态五部曲
确定dp数组（dp table）以及下标的含义
构造一维数组， dp[i] 表示以位置 i 结尾的最长递增子序列的长度。
显然， dp[0] = 1 （数组初始化）。
确定递推公式（状态转移方程）
基础情况是，对于任何位置 i，至少有一个长度为 1 的递增子序列，即 dp[i] = 1。
对于位置 i 的元素 nums[i]，我们检查所有位置 j < i 且 nums[j] < nums[i] 的元素，这意味着 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面形成一个新的更长的递增子序列。因此，我们可以更新 dp[i] = max(dp[i], dp[j] + 1)，表示以 nums[i] 结尾的最长递增子序列长度可能是之前某个较小子序列长度加一。
推导出
最长递增子序列最终代码
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(1); // 初始化 dp 数组，每个元素至少代表长度为1的子序列
let maxLength = 1; // 最长递增子序列的初始长度设为1
for (let i = 1; i < nums.length; i++) {// 动态规划填表过程
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {// 如果当前元素大于前一个元素，则可以构成递增子序列
dp[i] = Math.max(dp[i], dp[j] + 1);// 更新 dp[i] 为以 i 结尾的最长递增子序列长度
}
}
maxLength = Math.max(maxLength, dp[i]);// 更新全局的最大长度
}
return maxLength;
}但是上面的代码并不是很很通用，比如如果要输出所有的递增子序列。
打印所有最长递增子序列
详细的推导过程，推荐阅读：
https://labuladong.online/algo/dynamic-programming/longest-increasing-subsequence/
https://writings.sh/post/algorithm-longest-increasing-subsequence
最长公共子序列法
这个问题可以转换为最长公共子序列问题。比如数组A [2,3,9,5,7,8,2]，则我们排序该数组得到数组A’ [2,2,3,5,7,8,9]，然后找出数组A和A’的最长公共子序列即可（DP数组从一维转道二维）。
那么最长最长公共子序列如何求解呢？
最长公共子序列
计算最长公共子序列（Longest Common Subsequence，简称 LCS）是一道经典的动态规划题目，大部分比较困难的字符串问题都和这个问题一个套路，比如说编辑距离。
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
首先理解一下子序列这个概念
理解子序列的概念
子序列：从一个序列中删除某些元素（或者不删除任何元素），不改变剩余元素的相对顺序，就可以得到一个子序列。例如，序列 abcde 的子序列包括 a、ab、ace、abcde 等等。
不连续性：子序列中的字符不要求在原序列中是连续的，但它们的顺序必须与原序列中的顺序一致。
子序列、子数组/子串、子集区别
子序列 : 是一个序列，可以通过删除一些元素而不改变其余元素的顺序从另一个序列派生。
例如， {A, B, D} 是序列的子序列 {A, B, C, D, E} 删除后获得 {C} 和 {E}.
子数组（子串）：原序列中必须连续的一段。
例如，字符串的子字符串 'apple' 是 'apple', 'appl', 'pple', 'app', 'ppl', 'ple', 'ap', 'pp', 'pl', 'le', 'a', 'p', 'l', 'e', ''.
子集 : 原始集合的任何可能组合。空集是任意数组的子集。子序列始终保持数组元素的相对顺序(即增加索引)，但对子集没有这种限制。
例如， {3, 1} 是一个有效的子集 {1, 2, 3, 4, 5}。
与 最长重复子数组 区别在于这里不要求是连续的了，但要有相对顺序，即："ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
在《双指针：对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等)》里面讲过，这里就不多讲了。可以参考最长重复子数组的思路来看此题！
子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。
最长公共子序列解题思路
子序列问题很可能涉及到两个字符串，比如前文最长公共子序列，
一般来说，这类问题都是让你求一个最长子序列，因为最短子序列就是一个字符嘛，没啥可问的。一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，原因很简单，你想想一个字符串，它的子序列有多少种可能？起码是指数级的吧，这种情况下，不用动态规划技巧，还想怎么着？
对于两个字符串求子序列的问题，都是用两个指针 i 和 j 分别在两个字符串上移动，大概率是动态规划思路。
既然要用动态规划，那么就适合动规五部曲分析：
确定dp数组（dp table）以及下标的含义
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。
比如说对于字符串 s1 和 s2，为了方便理解此表，所以索引是从 1 开始的（代码从0开始）
示例2： 
dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。
既然要用动态规划，那就要定义 dp 数组，找状态转移关系。我们说的两种思路模板，就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。
第一种思路模板是一个一维的 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] 中，我们要求的子序列（最长递增子序列）的长度是 dp[i]。
为啥最长递增子序列需要这种思路呢？前文说得很清楚了，因为这样符合归纳法，可以找到状态转移的关系，这里就不具体展开了。
第二种思路模板是一个二维的 dp 数组：
int n = arr.length; int[][] dp = new dp[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i] == arr[j]) dp[i][j] = dp[i][j] + ... else dp[i][j] = 最值(...) } }这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列，比如「最长公共子序列」
涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列（最长公共子序列）长度为 dp[i][j]。
只涉及一个字符串/数组时（比如本文要讲的最长回文子序列），dp 数组的含义如下：在子数组 array[i..j] 中，我们要求的子序列（最长回文子序列）的长度为 dp[i][j]。
确定递推公式（状态转移方程）
主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
代码如下：
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}下面看下更加详细的推导：
状态转移说简单些就是做选择，比如说这个问题，是求 s1 和 s2 的最长公共子序列，不妨称这个子序列为 lcs。那么对于 s1 和 s2 中的每个字符，有什么选择？很简单，两种选择，要么在 lcs 中，要么不在。
这个「在」和「不在」就是选择，关键是，应该如何选择呢？这个需要动点脑筋：如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列嘛。
所以本题的思路是这样：
用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中；
否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。
先看一下递归解法（暴力解法），比较容易理解：
function longestCommonSubsequence(str1, str2) { function dp(i, j) { if (i === -1 || j === -1) return 0;// 空串的 base case if (str1[i] === str2[j]) return dp(i - 1, j - 1) + 1;// 空串的 base case return Math.max(dp(i - 1, j), dp(i, j - 1)); // 谁能让 lcs 最长，就听谁的 } return dp(str1.length - 1, str2.length - 1); }对于 s1[i] 和 s2[j] 不相等的情况，至少有一个字符不在 lcs 中，会不会两个字符都不在呢？比如下面这种情况：
所以代码是不是应该考虑这种情况，改成这样：
if str1[i - 1] == str2[j - 1]: # ... else: dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])其实可以这样改，也能得到正确答案，但是多此一举，因为 dp[i-1][j-1] 永远是三者中最小的，max 根本不可能取到它。
原因在于我们对 dp 数组的定义：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。
这样一看，显然 dp[i-1][j-1] 对应的 lcs 长度不可能比前两种情况大，所以没有必要参与比较。
dp数组如何初始化
先看看dp[i][0]应该是多少呢？
test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0；同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。
确定遍历顺序
从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。
举例推导dp数组
以输入：text1 = "abcde", text2 = "ace" 为例，dp状态如图：
最后红框dp[text1.size()][text2.size()]为最终结果
最终代码
const longestCommonSubsequence = (text1, text2) => {
let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));
for(let i = 1; i <= text1.length; i++) {
for(let j = 1; j <= text2.length; j++) {
if(text1[i-1] === text2[j-1]) {
dp[i][j] = dp[i-1][j-1] +1;;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[text1.length][text2.length];
};两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。
示例 1：输入: word1 = "sea", word2 = "eat" 输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
两个字符串的删除操作解题思路
题目让我们计算将两个字符串变得相同的最少删除次数，那我们可以思考一下，最后这两个字符串会被删成什么样子？
删除的结果不就是它俩的最长公共子序列嘛！
那么，要计算删除的次数，就可以通过最长公共子序列的长度推导出来：
function minDistance( s1, s2) {
const m = s1.length(), n = s2.length();
const lcs = longestCommonSubsequence(s1, s2); // 复用前文计算 lcs 长度的函数
return m - lcs + n - lcs;
}两个字符串的最小ASCII删除和 ，不讲了。
最长回文子序列
俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
示例 1：输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
这道题目其实是最长递增子序列的一个变种，因为每次合法的嵌套是大的套小的，相当于在二维平面中找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。
前面说的标准 LIS 算法只能在一维数组中寻找最长子序列，而我们的信封是由 (w, h) 这样的二维数对形式表示的，如何把 LIS 算法运用过来呢？
读者也许会想，通过 w × h 计算面积，然后对面积进行标准的 LIS 算法。但是稍加思考就会发现这样不行，比如 1 × 10 大于 3 × 3，但是显然这样的两个信封是无法互相嵌套的。
这道题的解法比较巧妙：
先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序；之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。
因为 宽度和高度都比这个信封大的时候，这个信封就才可放进另一个信封里！举个例子：
对宽度进行升序高度降序，从而防止了错误的嵌套。比如：信封A: (5, 4) 、信封B: (5, 6)、信封C: (5, 2)
如果仅对宽度进行升序排序，则为：信封:C(5, 2)、信封A:(5, 4),、信封B:（5, 6)，这会导致在计算LIS时，信封B可能被错误地嵌套在信封A中——因为信封B的宽度和信封A是一样的，它们不能嵌套！
画个图理解一下，先对这些数对进行排序：
然后在 h 上寻找最长递增子序列，这个子序列就是最优的嵌套方案：
那么为什么这样就可以找到可以互相嵌套的信封序列呢？稍微思考一下就明白了：
首先，对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套，所以我们只需要专注高度 h 这个维度能够互相嵌套即可。
其次，两个 w 相同的信封不能相互包含，所以对于宽度 w 相同的信封，对高度 h 进行降序排序，保证二维 LIS 中不存在多个 w 相同的信封（因为题目说了长宽相同也无法嵌套）。
最终代码
var maxEnvelopes = function(envelopes) {// 按宽度升序排列，如果宽度一样，则按高度降序排列
envelopes.sort((a,b)=>a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
const n = envelopes.length;
const height = new Array(n);// 对高度数组寻找 LIS
for (let i = 0; i < n; i++) height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
var lengthOfLIS = function(nums) {
// 见前文,最长递增子序列
}为了清晰，我将代码分为了两个函数， 你也可以合并，这样可以节省下 height 数组的空间。
当然，对于每件物品都是通过「二分」找到其前一件物品，可以使时间复杂度从O(n^2)变为O(NlogN)
参考文章：
经典动态规划：最长公共子序列 https://www.cnblogs.com/labuladong/p/13945482.html
子序列问题模板 https://labuladong.github.io/zgnb/3/15/20/
最长递增子序列 - 动态规划方法及打印 https://writings.sh/post/algorithm-longest-increasing-subsequence
最长递增子序列 https://www.iteye.com/blog/qiemengdao-1660229
https://acoier.com/2021/03/04/354.%20俄罗斯套娃信封问题（困难）/
转载本站文章《DP笔记(5)：双串线性DP问题，从回文字串到子序列问题模板》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9113.html