最长公共子序列

最长公共子序列

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];
        //填充元素0
        for(int i = 0;i < dp.length;i++){
            Arrays.fill(dp[i],0);
        }
        
        for(int i = 1;i < m + 1;i++){
            for(int j = 1;j < n + 1;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]);
                }
            }
        }
        int max = 0;
        for(int i = 0;i <= m;i++){
            for(int j = 0;j <= n;j++){
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
}