最长公共子序列

最长公共子序列问题，给定两个字符串str1和str2，str1 = “2A3V45678”，str2=“1@#2X3V45”，返回“23V45”

. 注意：子序列不要求出现的顺序必须连续。

题目地址：Leetcode1143

暴力搜索：

两个字符串的末尾开始往回找，两个指针i，j分别指向str1的末尾和str2的末尾。若 str1【i】 == str2【j】则公共子序列+1，否则i向前移动一位或者j向前移动一位，判断此时以i或者j结尾的字符串的最长公共子序列，然后选择较大值，不停的递归，直到有一个指针为-1，返回。

private int[][] dp;
    public int longestCommonSubsequence(String text1, String text2) {
        dp = new int[text1.length()][text2.length()];
        return dfs(text1,text2,text1.length()-1,text2.length()-1);
    }
    
    public int dfs(String str1,String str2,int ii,int jj){
        if(ii == -1 || jj == -1) return 0;
        if(dp[ii][jj] != 0) return dp[ii][jj];
        if(str1.charAt(ii) == str2.charAt(jj)){
            dp[ii][jj] = dfs(str1,str2,ii-1,jj-1)+1;
            return dp[ii][jj];
        }else{
            dp[ii][jj] = Math.max(dfs(str1,str2,ii-1,jj), dfs(str1,str2,ii,jj-1));
            return dp[ii][jj];
        }
    }

DP分析：

使用一个二维数组 dp【M】【N】来表示状态，其中M、N分别为str1和str2的长度，对于任意的dp【i】【j】表示str1【0.。。。i】的子串与str2【0.。。。j】的字串的最长公共字串长度。所以

初始状态为：

dp【0】【0.。。N-1】第一行为str1的第一个元素和str2中字串的最长公共字串，假如str1【0】== str2【j】，则dp【0】【j】 = 1，并且dp【0】【j。。。N-1】 = 1. 同理对于第一列进行初始化。

状态转移方程：

对于dp【i】【j】而言，有三种情况需要考虑

1. dp【i】【j】可能等于dp【i-1】【j】
2. dp【i】【j】可能等于dp【i】【j-1】
3. dp【i】【j】可能等于dp【i-1】【j-1】+1，其中必须满足str1【i】==str2【j】

最终dp【i】【j】取以上三者中的最大值即可。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()][text2.length()];
        int max = 0;

        //初始化
        for(int i=0;i<text2.length();i++){
            if(text2.charAt(i) == text1.charAt(0)){
                for(int j=i;j<text2.length();j++){
                    dp[0][j] = 1;
                }
                max = 1;
                break;
            }
        }
        for(int i=0;i<text1.length();i++){
            if(text1.charAt(i) == text2.charAt(0)){
                for(int j=i;j<text1.length();j++){
                    dp[j][0] = 1;
                }
                max = 1;
                break;
            }
        }
        
        //递推
        for(int i=1;i<text1.length();i++){
            for(int j=1;j<text2.length();j++){
                int a = dp[i-1][j];
                int b = dp[i][j-1];
                int c = Integer.MIN_VALUE;
                if(text1.charAt(i) == text2.charAt(j)){
                    c = dp[i-1][j-1] + 1;
                }
                dp[i][j] = Math.max(a,Math.max(b,c));
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
}