Location>code7788 >text

Linear dp: LeetCode516 . Longest palindromic subsequence

Popularity：351 ℃/2024-09-07 16:39:11

LeetCode516 . Longest palindromic subsequence

Title Narrative:

Power Button Title Link (opens new window)

Here's a string for you.s , find the longest subsequence of echoes among them and return the length of that sequence.

A subsequence is defined as a sequence formed by deleting some characters or not deleting any characters without changing the order of the remaining characters.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: a possible longest palindromic subsequence is "bbbb" .

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: a possible longest palindromic subsequence is "bb" .

Tip:

  • 1 <= <= 1000
  • s Consists of lowercase letters only

Dynamic Planning Ideas

  • We've covered this above.palindromeThen we can follow thepalindromethe idea of solving this problem, but we first have to be clear about thepalindromecap (a poem)palindromeexclusionary rule

  • LeetCode647. palindromic substringsThe question asks for a substring of echoes, while the question asks for a sequence of echoes, so it's important to understand the difference between the two.

  • A palindrome substring is meant to be continuous; a palindrome subsequence is not! Echo substrings, and echo subsequences are all classic topics in dynamic programming.

  • Back to the text substring, you can do both:

    • 647. Hui Wen Zi Skewer

    • 5. Longest palindrome substring

The idea is really similar, but this question is a little easier than finding the substring of the palindrome because there are fewer cases.

The five-part analysis of the moving regulation is as follows:

1. Identify state variables and their meanings

  • We set up the dp array, dp[i]] [j] to represent the s-string in the[i，j]The length of the longest echo subsequence in the range. (j>=i）
  • Then we establish the state variabledp[i][j], then we have to start dealing with recursive formulas and how to initialize the

2. Determine the recursive formula

  • The most important thing we can do here is to judges[i],s[j]Relationship between
    • s[i]==s[j] At this point.dp[i][j]=dp[i+1][j-1]+2
  • Why is it +2? Because this question is the longest palindromic subsequence whens[i]==s[j]when[i,j]There are at leastdp[i+1][j-1]+2The longest echo subsequence of this size, +2 is the addition of thes[i],s[j]These two characters.

516.最长回文子序列

  • in the event thats[i] is not the same as s[j]Descriptions[i] and s[j]Adding it at the same time doesn't increase the number of[i,j]The length of the interval echo subsequence, then adding separately thes[i]、s[j]See which one can form the longest palindromic subsequence.

become a members[j]The length of the echo subsequence ofdp[i + 1] [j]。

become a members[i]The length of the echo subsequence ofdp[i] [j - 1]。

in that casedp [i] [j]It must be taken to the maximum, i.e:dp [i] [j] = max(dp [i + 1] [j], dp[i] [j - 1]);

516.最长回文子序列1

3. How to initialize the dp array

  • First, we have to deal with the special case wheni==jThe time, this time in the[i,j]There is only one character in the range, usedp[i][j]=dp[i+1][j-1]+2 will cause the left boundary of the currently processed substring to be larger than the right boundary, at which point we will have to deal with it in a special way, when the processed substring has only one character, thei==jfurthermoredp[i][j]Clearly equal to 1, since a single character is also a palindrome subsequence, and the length of this palindrome subsequence is 1.
vector<vector<int>> dp((), vector<int>((), 0));
for (int i = 0; i < (); i++) dp[i][i] = 1;

4. Determining the order of traversal

From the recursive formula, it follows thatdp[i][j] depend ondp[i + 1][j - 1] ，dp[i + 1][j] and dp[i][j - 1], as shown:

img

  • So that means we want to getdp[i][j] , which must start at the bottom left and recurse in the direction of the top right.
  • So the traversal order is bottom to top, left to right
        // Start assigning values to the dp array from bottom to top and left to right.
        for(int i=()-1;i>=0;i--){
            for(int j=i+1;j<();j++){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
            }
        }

5. Example of printing a dp array

Enter s: "cbbd" as an example, and the state of the dp array is shown:

516.最长回文子序列3

The red box that is:dp[0][() - 1]; for the final result.

Final Code:

// longest palindromic subsequence
class Solution {
public.
    int longestPalindromeSubseq(string s) {
        // Create a two-dimensional array of dp's
        vector<vector<int>> dp((),vector<int>((),0));
        //Initialize the dp array, first of all, when i and j are equal, that is, there is only a subsequence of one character, its dp value is assigned to 1
        for(int i=0;i<();i++) dp[i][i]=1;
        // Start assigning values to the dp array from bottom to top and left to right.
        for(int i=()-1;i>=0;i--){
            for(int j=i+1;j<();j++){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
            }
        }
        // Finally, the length of the longest echo subsequence in the range from ()-1 is the answer we need.
        return dp[0][()-1].
    }
};

clearly indicate

  • The author is quoted in this articleCode RandomizerFor a more in-depth look at some of the images and the original article, go to the original author's article and read it!
  • Code Randomizer
<Previous Next>