子序列问题模板

动态规划之子序列问题解题模板 §

通知：数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！另外，建议你在我的 网站 学习文章，体验更好。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
1312. Minimum Insertion Steps to Make a String Palindrome	1312. 让字符串成为回文串的最少插入次数	🔴
516. Longest Palindromic Subsequence	516. 最长回文子序列	🟠

-----------

子序列问题是常见的算法问题，而且并不好解决。

首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。

而且，子序列问题很可能涉及到两个字符串，比如前文 最长公共子序列，如果没有一定的处理经验，真的不容易想出来。所以本文就来扒一扒子序列问题的套路，其实就有两种模板，相关问题只要往这两种思路上想，十拿九稳。

一般来说，这类问题都是让你求一个最长子序列，因为最短子序列就是一个字符嘛，没啥可问的。一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。

原因很简单，你想想一个字符串，它的子序列有多少种可能？起码是指数级的吧，这种情况下，不用动态规划技巧，还想怎么着？

既然要用动态规划，那就要定义 dp 数组，找状态转移关系。我们说的两种思路模板，就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。

一、两种思路 §

---

引用本文的文章

• 动态规划设计：最长递增子序列
• 如何判断回文链表
• 对动态规划进行降维打击
• 最优子结构原理和 dp 数组遍历方向
• 经典动态规划：最长公共子序列

---

＿＿＿＿＿＿＿＿＿＿＿＿＿

本文为会员内容，请扫码关注公众号或 点这里 查看：

====其他语言代码====

516.最长回文子序列

javascript §

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    let l = s.length;
    if (l <= 1) {
        return l;
    }
		
    // 初始化一个 dp[l][l]
    let dp = new Array(l);
    for (let i = 0; i < l; i++) {
        dp[i] = new Array(l);
        dp[i].fill(0, 0, l)
      	// // base case
        dp[i][i] = 1
    }
  
    // 从右下角开始，逐渐往上推
    for (let i = l - 2; i >= 0; i--) {
        for (let j = i + 1; j <= l - 1; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(
                    dp[i + 1][j],
                    dp[i][j - 1]
                )
            }
        }
    }
    return dp[0][l - 1]
};