# 动态规划之子序列问题解题模板
![](https://labuladong.github.io/pictures/souyisou1.png) **通知:算法可视化编辑器上线,[点击体验](https://labuladong.online/algo/intro/visualize/)!另外,建议你在我的 [网站](https://labuladong.online/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` 数组定义来解决。 ### 一、两种思路