Subsequence Problem Patterns for DP
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| 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.