LeetCode1143. 最长公共子序列

思路

动规五部曲

1.定义dp数组

dp[i][j]表示第一个字符串前i-1个字符和第二个字符串中前j-1个字符中存在的最长公共子序列为dp[i][j]。如果定义为i的话就会很遍历和初始化的时候会很麻烦。

2.递推公式

如果小标为i和j的字符相等则dp[i][j]=dp[i-1][j-1] 1

如果不相等则dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])

1.  
   if(a==b){
2.  
   dp[i][j]=dp[i-1][j-1] 1;
3.  
   }else{
4.  
   dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
5.  
   }

3.初始化 

根据递推公式和定义可以知道应该初始化为0.那就直接用默认值不初始化即可。

4.遍历顺序

根据递推公式，可以知道是正序遍历。

5.打印顺序

dp数组中最大的就是最后的结果。

代码

1.  
   class Solution {
2.  
   public int longestCommonSubsequence(String text1, String text2) {
3.  
   int dp[][] = new int[text1.length() 1][text2.length() 1];
4.  
    
5.  
   for(int i=1;i<=text1.length();i ){
6.  
   char a = text1.charAt(i - 1);
7.  
   for(int j = 1;j<=text2.length();j ){
8.  
   char b=text2.charAt(j-1);
9.  
   if(a==b){
10.  
    dp[i][j]=dp[i-1][j-1] 1;
11.  
    }else{
12.  
    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
13.  
    }
14.  
    }
15.  
    }
16.  
    int max=0;
17.  
    for(int i = 0;i<=text1.length();i ){
18.  
    for(int j = 0;j<=text2.length();j ){
19.  
    max=Math.max(max,dp[i][j]);
20.  
    }
21.  
    }
22.  
    return max;
23.  
    }
24.  
    }

这篇好文章是转载于：学新通技术网