DP subsequence series problem

 

package LeetCode.DP;

public class OfferII095 {
    public int longestCommonSubsequence(String text1, String text2) {
            int n=text1.length();
            int m=text2.length();
            return helper(text1,0,text2,0);
    }

    private int  helper(String text1, int n, String text2, int m) {
        if(n==text1.length()||m==text2.length()){
            return 0;
        }
        if(text1.charAt(n)==text2.charAt(m)){
            // The current two characters are the same 
            return 1+helper(text1,n+1,text2,m+1);
        }else {
            return Math.max(Math.max(helper(text1,n+1,text2,m+1),helper(text1,n+1,text2,m)),
                    helper(text1,n,text2,m+1));
        }
    }
}

•   There is an optimization point , It's when we compare larger lengths , There is no need to compare helper(text1,n+1,text2,m+1), because n+1,m+1 The range of both strings of is less than n+1,m and n,m+1 String length of , So it must be shorter than the common subsequence of these two
• Why not recurse from front to back , Turn semantics into pre n Characters and before m The length of the longest common sequence of characters , Because when we compare a character , Our recursion is a recursive function that depends on a smaller range , That's not right , If we encounter a different character , We should compare the current character with the following character , See if you can find the same characters , If you define semantics like this , We just compare with the previous characters , That's not right , Because the recursive semantics is that the previous strings are better , It's meaningless to compare again

Pruning optimization

class Solution {
  public int longestCommonSubsequence(String text1, String text2) {
        int n=text1.length();
        int m=text2.length();
        int dp[][]=new int[n+1][m+1];
        for (int []rows:dp) {
            Arrays.fill(rows,-1);
        }
            return helper(text1,0,text2,0,dp);
    }

    private int  helper(String text1, int n, String text2, int m, int[][] dp) {
        if(n==text1.length()||m==text2.length()){
            return 0;
        }
        if (dp[n][m]!=-1){
            return dp[n][m];
        }
        if(text1.charAt(n)==text2.charAt(m)){
            // The current two characters are the same 
            dp[n][m]= 1+helper(text1,n+1,text2,m+1, dp);
            return dp[n][m];
        }else {
            dp[n][m] =Math.max(helper(text1,n+1,text2,m, dp), helper(text1,n,text2,m+1, dp));
            return dp[n][m];
        }
    }
}

Bottom up dynamic planning

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n=text1.length();
        int m=text2.length();
        int dp[][]=new int[n+1][m+1];
        for (int i =1; i <=n; i++) {
            for (int j =1; j <=m; j++) {
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
}

•   Use functions f(i, j) Representation string s1 Subscript from 0 Start to i Substring of s1[0...i] And string s2 Subscript from 0 Start to j Substring of s2[0...j] The length of the longest common subsequence of . about f(i, j), If s1[i] == s2[j], So it's equivalent to s1[0...i - 1] and s2[0...j - 1] Add a common character after the longest common subsequence of , That is to say f(i, j) = f(i - 1, j - 1) + 1. If s1[i] != s2[j], Then these two characters cannot appear in s1[0...i] and s2[0...j] In the common subsequence of . here s1[0...i] and s2[0...j] The longest common subsequence of is s1[0...i - 1] and s2[0...j] The longest common subsequence and s1[0...i] and s2[0...j - 1] The larger value in the longest common subsequence of , namely f(i, j) = max(f(i - 1, j), f(i, j - 1)). So the transition equation of state is