Leetcode 1143. dynamic programming of the longest common subsequence /medium

---

1.Description

Given two strings text1 and text2, Returns the longest of these two strings Common subsequence The length of . If it doesn't exist Common subsequence , return 0 .

A string of Subsequence This is a new string ： It is to delete some characters from the original string without changing the relative order of the characters （ You can also delete no characters ） After the composition of the new string .

for example ,“ace” yes “abcde” The subsequence , but “aec” No “abcde” The subsequence .
Two strings of Common subsequence Is the subsequence shared by these two strings .

---

2.Example

 Example  1：
 Input ：text1 = "abcde", text2 = "ace" 
 Output ：3  
 explain ： The longest common subsequence is  "ace" , Its length is  3 .

 Example  2：
 Input ：text1 = "abc", text2 = "abc"
 Output ：3
 explain ： The longest common subsequence is  "abc" , Its length is  3 .

 Example  3：
 Input ：text1 = "abc", text2 = "def"
 Output ：0
 explain ： The two strings have no common subsequence , return  0 .

---

3.Solution

Reference resources ： Add link description

First , Distinguish between two concepts ： Subsequences can be discontinuous ; Subarray （ Substring ） The need is continuous ;
in addition , Dynamic programming also has a routine ： When a single array or string needs dynamic programming , Dynamic programming can be dp[i] Defined as nums[0:i] I want to ask for the results ; When two arrays or strings need dynamic programming , Dynamic programming can be defined as two-dimensional dp[i][j] , Its meaning is in A[0:i] And B[0:j] Match to get the desired result .

1. State definition

For example, for this topic , Can define dp[i][j] Express text1[0:i-1] and text2[0:j-1] The longest common subsequence of . （ notes ：text1[0:i-1] It means text1 Of The first 0 Elements to i - 1 Elements , Both ends contain ）
The reason dp[i][j] The definition of is not text1[0:i] and text2[0:j] , It's for the convenience of being i = 0 perhaps j = 0 When ,dp[i][j] Represents a match between an empty string and another string , such dp[i][j] It can be initialized to 0.

2. State transition equation

After knowing the state definition , We begin to write the state transition equation .

When text1[i - 1] == text2[j - 1] when , Indicates that the last bit of the two substrings is equal , So the longest common subsequence is added 1, therefore dp[i][j] = dp[i - 1][j - 1] + 1; for instance , For example, for ac and bc for , The length of their longest common subsequence is equal to a and c The longest common subsequence length of 0 + 1 = 1.
When text1[i - 1] != text2[j - 1] when , Indicates that the last bit of two substrings is not equal , Then the state at this time dp[i][j] Should be dp[i - 1][j] and dp[i][j - 1] The maximum of . for instance , For example, for ace and bc for , The length of their longest common subsequence is equal to ① ace and b The longest common subsequence length of 0 And ② ac and bc The longest common subsequence length of 1 The maximum of , namely 1.
To sum up, the state transition equation is ：

dp[i][j] = dp[i - 1][j - 1] + 1, When text1[i - 1] == text2[j - 1];
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), When text1[i - 1] != text2[j - 1]

3. Initialization of state

Initialization is to see when i = 0 And j = 0 when , dp[i][j] What should be the value .

When i = 0 when ,dp[0][j] It means text1 Empty string in Follow text2 The longest common subsequence of , The result must be 0.
When j = 0 when ,dp[i][0] It means text2 Empty string in Follow text1 The longest common subsequence of , The result must be 0.
Sum up , When i = 0 perhaps j = 0 when ,dp[i][j] Initialize to 0.

4. Traversal direction and range

because dp[i][j] Depend on and depend on dp[i - 1][j - 1] , dp[i - 1][j], dp[i][j - 1], therefore ii and jj The traversal order of must be from small to large .
in addition , Because when ii and jj The value is 0 When ,dp[i][j] = 0, and dp The array itself is initialized to 0, therefore , Directly to ii and jj from 1 To traverse the . The end of the traversal should be the length of the string len(text1)len(text1) and len(text2)len(text2).

5. The final result

because dp[i][j] The meaning is text1[0:i-1] and text2[0:j-1] The longest common subsequence of . What we ultimately want is text1 and text2 The longest common subsequence of . So the result to be returned is i = len(text1) also j = len(text2) At the time of the dp[len(text1)][len(text2)].

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        int M = text1.length();
        int N = text2.length();
        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)) {
    
        			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[M][N];
    }
}