1. Longest common substring

Refer to the link

The most important thing in dynamic programming is to find the subproblems that can be recursed, and then list the recursion formula, and finally search and fill in the table.

The table space size is usually O(N2). But in general, since recursion only relates to the previous row, it can be optimized to O(N).

Given two strings S1 and S2 of length n1 and n2 respectively, about their longest common substring, DP equation is as follows:

L[i,j] = ( S1[i] == s2[j] ? L[i-1,j-1]+1 : 0 );

Where L[I,j] represents the length of the common substring ending with the I and j characters in S1 and S2.

To find the longest common substring, we iterate through the n1 * n2 table space. The code is as follows:

public String DPlengthOfLongestCommonSubstring(String s1, String s2){
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
        return "";
    }
    int start = 0;
    int maxLen = 0;
    int [][] table = new int[s1.length()][s2.length()];
    for (int i = 0; i < s1.length(); i++) {
        for (int j = 0; j < s2.length(); j++) {
            if (i == 0 || j == 0){
                if (s1.charAt(i) == s2.charAt(j)){
                    table[i][j] = 1;
                }
                if (table[i][j] > maxLen){
                    maxLen = table[i][j];
                    start = i;
                }
            }else {
                if (s1.charAt(i) == s2.charAt(j)){
                    table[i][j] = table[i-1][j-1] + 1;
                }
                if (table[i][j] > maxLen){
                    maxLen = table[i][j];
                    start = i + 1 - maxLen;
                }
            }
        }
    }
    return s1.substring(start, start + maxLen);
}
Copy the code

2. Longest common subsequence

Longest common subsequence

Difficulty: Medium

Dp [I][j] saves the longest common subsequence before S [I] t[j]

dp[i][j] = dp[i-1][j-1] + 1 (s[i]==t[j]) Math.max(dp[i][j-1], dp[i-1][j]) (s[i]! =t[j])

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    if(m == 0 || n == 0) return 0;
    int[][] dp = new int[m+1][n+1];

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(text1.charAt(i-1) == text2.charAt(j-1)){  //i-1  j-1
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else{
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }
    }

    return dp[m][n];
}Copy the code