动态规划之子序列问题解题模板
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 1312. Minimum Insertion Steps to Make a String Palindrome | 🔴 |
| 516. Longest Palindromic Subsequence | 🟠 |
Subsequence problems are common algorithmic challenges and can be quite tricky to solve.
Firstly, subsequence problems are inherently more difficult than substring or subarray problems. This is because subsequences are non-continuous sequences, whereas substrings and subarrays are continuous. Even exhaustive enumeration can be challenging, let alone solving related algorithmic problems.
Moreover, subsequence problems often involve two strings, such as in the previous article Longest Common Subsequence. Without some experience in handling these, it can be hard to come up with a solution. So, let's dive into the patterns of subsequence problems. There are essentially two templates. If you think along these two lines, you'll be pretty confident in solving related problems.
Generally, these problems ask you to find the longest subsequence, because the shortest subsequence is just a single character, which isn't much of a question. Once it involves subsequences and optimization (like finding the maximum or minimum), it's almost certain that the problem is testing your dynamic programming skills, with a time complexity typically around O(n^2).
The reason is simple: think about a string and how many possible subsequences it can have. It's at least exponential. In such cases, without using dynamic programming, what other approach could be effective?
Since we're using dynamic programming, we need to define a dp array and find the state transition relations. The two thinking templates we mentioned are essentially about how to define the dp array. Different problems may require different dp array definitions to solve.