516. Longest subroutine sequence: interval DP solves the longest subroutine sequence problem

This is the 12th day of my participation in the August Text Challenge.More challenges in August

Topic describes

This is the 516. Longest sequence of subrons on LeetCode with medium difficulty.

Tag: “Dynamic programming”, “interval DP”

Given a string s, find the longest sequence of subroutines and return the length of that sequence.

A subsequence is defined as a sequence in which some characters or none of the characters are deleted without changing the order of the remaining characters.

Example 1:

Input: s = "bbbab" Output: 4 Explanation: The longest possible sequence of subroutines is "BBBB".Copy the code

Example 2:

Input: s = "CBBD" Output: 2 Explanation: The longest possible sequence of subrons is "bb".Copy the code

Tip:

• 1 <= s.length <= 1000
• The “S” is a lowercase letter only

Dynamic programming

This is a classic interval DP problem.

The reason why interval DP can be used for solving is that on the basis of a given palindrome string, if two new characters are added to the edge of the palindrome string, whether the new string is palindrome can be determined by judging whether the two characters are equal.

That is to say, the palindrome state value of the large interval can be derived from the palindrome state value between cells.

In the sense of graph theory, any length is zero
$len$The palindrome string of, must be formed by “length is
$len – 1$“Or” Length is
$len – 2$“Palindrome string transferred.

There is a topological order between two palindromic strings with common palindromic parts (there is a directed edge from a “smaller” palindromic string to a “larger” palindromic string).

Generally, interval DP problems are, and the common basic flow is:

1. Enumerating interval size from small to large Lenlenlen
2. Enumerates the left end point of the interval LLL, and calculates the right end point of the interval r= L + Len −1r = L + len-1 r= L + Len −1 according to the interval size Lenlenlen and the left end point
3. Find the value of f[L][r]f[L][r]f[L][r]f[L][r]

Therefore, we define f [l] [l] [r] [r] f f [l] [r] for interval [l, r] [l, r] [l, r] how much is the longest sequence length is back to the text.

F [l][r]f[l][r]f[l][r] f[l][r] how to transfer.

Since our state definition does not restrict the palindrome string to s[l]s[L]s[l]s[l] or s[r]s[r]s[r] s[r]s[r].

The boundary characters s[l]s[l]s[l] s[l]s[r]s[r]s[r] s[r]s[r] f[l] f[l][r]f[l][r]f[l][r] f[l][r]

• Form palindrome string must not contain s [l] [l] and [l] s s s s [r] [r] [r] s, namely completely does not consider s [l] [l] and [l] s s s s [r] [r] [r] s:

• The resulting palindrome string may contain s[l]s[l]s[l] s[l], but must not contain s[r]s[r]s[r] s[r] :

• The resulting palindrome string may contain s[r]s[r]s[r] s[r], but must not contain s[l]s[l]s[l] s[l] :

• Formation of palindrome string may contain s [l] s [l], [l] s may contain s [r] [r] [r] s s, according to the s [l] [l] and [l] s s s s [r] [r] [r] s is equal to:

It should be noted that the above situations can ensure “no leakage”, but not “no gravity”. For the problem of finding the maximum value, we only need to ensure “no leakage”. The repeated participation of some states in the comparison will not affect the correctness of the results.

Some details: We need to specifically rule out two base cases of length 111 and 222. When the length is 111, it must be a palindrome, when the length is 222, and if and only if two characters are equal.

Code:

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[][] f = new int[n][n]; 
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                if (len == 1) {
                    f[l][r] = 1;
                } else if (len == 2) {
                    f[l][r] = cs[l] == cs[r] ? 2 : 1;
                } else {
                    f[l][r] = Math.max(f[l + 1][r], f[l][r - 1]);
                    f[l][r] = Math.max(f[l][r], f[l + 1][r - 1] + (cs[l] == cs[r] ? 2 : 0)); }}}return f[0][n - 1]; }}Copy the code

• O(n2)O(n^2)O(n2)
• Space complexity: O(n2)O(n^2)O(n2)

The last

This is the No.516 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.