# 动态规划之子序列问题解题模板
**通知：[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0；[第 13 期刷题打卡](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q) 最后一天报名！另外，建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章，体验更好。**
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [1312. Minimum Insertion Steps to Make a String Palindrome](https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/) | [1312. 让字符串成为回文串的最少插入次数](https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/) | 🔴
| [516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/) | [516. 最长回文子序列](https://leetcode.cn/problems/longest-palindromic-subsequence/) | 🟠
**-----------**
子序列问题是常见的算法问题，而且并不好解决。
首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。
而且，子序列问题很可能涉及到两个字符串，比如前文 [最长公共子序列](https://labuladong.github.io/article/fname.html?fname=LCS)，如果没有一定的处理经验，真的不容易想出来。所以本文就来扒一扒子序列问题的套路，其实就有两种模板，相关问题只要往这两种思路上想，十拿九稳。
一般来说，这类问题都是让你求一个**最长子序列**，因为最短子序列就是一个字符嘛，没啥可问的。一旦涉及到子序列和最值，那几乎可以肯定，**考察的是动态规划技巧，时间复杂度一般都是 O(n^2)**。
原因很简单，你想想一个字符串，它的子序列有多少种可能？起码是指数级的吧，这种情况下，不用动态规划技巧，还想怎么着？
既然要用动态规划，那就要定义 `dp` 数组，找状态转移关系。我们说的两种思路模板，就是 `dp` 数组的定义思路。不同的问题可能需要不同的 `dp` 数组定义来解决。
### 一、两种思路
引用本文的文章
- [动态规划设计：最长递增子序列](https://labuladong.github.io/article/fname.html?fname=动态规划设计：最长递增子序列)
- [如何判断回文链表](https://labuladong.github.io/article/fname.html?fname=判断回文链表)
- [对动态规划进行降维打击](https://labuladong.github.io/article/fname.html?fname=状态压缩技巧)
- [最优子结构原理和 dp 数组遍历方向](https://labuladong.github.io/article/fname.html?fname=最优子结构)
- [经典动态规划：最长公共子序列](https://labuladong.github.io/article/fname.html?fname=LCS)
**＿＿＿＿＿＿＿＿＿＿＿＿＿**
应合作方要求，本文不便在此发布，请扫码关注回复关键词「子序列」或 [点这里](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_62987943e4b01c509ab8b6aa/1) 查看：
======其他语言代码======
[516.最长回文子序列](https://leetcode-cn.com/problems/longest-palindromic-subsequence)
### javascript
```js
/**
* @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]
};
```
