This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First, the topic overview

Subsequence problem is the most common algorithm problem, and it is not easy to solve.

Once you get into subsequences and maxima, you’re almost certainly looking at dynamic programming techniques, and the time is usually O(n ^ 2).

Since we use dynamic programming, we need to define dp arrays and look for state transition relationships.

Two ideas:

  1. The first idea template is one-dimensionaldpArray:
int n = array.length;
int [] dp = new int[n];

for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {dp[I] = Max (dp[I], dp[j] +... }}Copy the code
  1. The second idea template is a two-dimensional onedpArray:
int n = arr.length;
int [][] dp = new int[n][n];

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        elseDp [I][j] = maximum value (...) }}Copy the code

LeetCode 516. Longest sequence of subroutines

Given a string s, find the longest sequence of subroutines and return the length of the sequence. We can assume that the maximum length of s is 1000.

Example 1: Input: "bbbab" Output: 4 The longest possible subroutine sequence is "BBBB". Example 2: Input: "CBBD" Output: 2 One of the longest possible subroutines is "bb".Copy the code

Dry problem analysis

For example, if you type s= “aecda”, the algorithm returns 3, because the longest sequence of subroutines is “ACA” with length 3

The problem defines the dp array as: in the substring S [I..j], the length of the longest subroutine sequence is dp[I][j].

Why is the problem defining a two-dimensional DP array like this?

Finding state transitions requires inductive thinking, which is how to deduce unknown parts from known results. This definition is easy to generalize and find state transitions.

Assuming we know the result of the subproblem dp[I + 1][j-1] (the length of the longest subroutine sequence in s[I + 1… j-1]), can we calculate the value of dp[I][j]?

Yes, depending on the s[I] and s[j] characters.

As shown in figure:

  1. ifs[i] == s[j]: So this two pluss[i+1...j-1]The longest sequence of rhymes ins[i...j]The longest sequence of subroutines of

As shown in figure:

  1. ifs[i] ! = s[j]: Means they couldn’t have been there at the same times[i...j]The longest sequence of subroutines, so add them separatelys[i+1...j-1]To see which substring produces a longer sequence of subtexts.

As shown in figure:

The logic is as follows:

if (s[i] == s[j])
    // They must be in the longest sequence of rhymes
    dp[i][j] = dp[i + 1][j - 1] + 2;
else 
    // s[I +1..j] or S [I.. J-1].
    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
Copy the code

The length of the longest subsequence of the entire S is dp[0][n-1].





Second, the idea of implementation

Ideas:

  1. Get the basics straightbase case: If the longest sequence length of a single character is 1,dp[i][j] = 1 (i == j)
  2. becauseiDefinitely less than or equal tojSo for thosei > jWhere there is no subsequence at all, initialized to zero

According to the state transition equation, dp[I][j] needs to know the three positions of DP [I + 1][J-1], DP [I + 1][j], dp[I][J-1], as shown in figure:

In order to ensure that every time dp[I][j] is calculated, the position of the lower left and right direction has been calculated, and it can only be traversed diagonally or backwards, as shown in the figure:

Choose reverse traversal here.

public class LeetCode_516 {
    / / Time: O (n ^ 2), Space: O (n ^ 2), Faster - : 74.25%
    public int longestPalindromeSubseq(String s) {

        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        int [][] dp = new int[n][n];

        for (int i = 0; i < n; ++i)
            dp[i][i] = 1;
        // Reverse traversal ensures correct state transition
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                // State transition equation
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); }}// The longest sequence length of the entire s
        return dp[0][n - 1]; }}Copy the code