public class _1143 {
    static class Solution1 {
        public int longestCommonSubsequence(String text1, String text2) {
            char[] ch1 = text1.toCharArray();
            char[] ch2 = text2.toCharArray();
            int[][] dp = new int[ch1.length + 1][ch2.length + 1];
            int max = 0;
            for (int i = 1; i <= ch1.length; i++) {
                for (int j = 1; j <= ch2.length; j++) {
                    if (ch1[i - 1] == ch2[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[ch1.length][ch2.length];
        }
    }

    static class Solution2 {
        public int longestCommonSubsequence(String text1, String text2) {
            // dp[i][j],以 text1 i为结尾，text2 以j为结尾，的最长子串
            Integer[][] dp = new Integer[text1.length()][text2.length()];
            return topToButtom(dp, text1.length() - 1, text2.length() - 1, text1, text2);
        }

        public int topToButtom(Integer[][] dp, int i, int j, String a, String b) {
            if (i < 0 || j < 0) return 0;
            if (dp[i][j] != null) return dp[i][j];
            if (a.charAt(i) == b.charAt(j)) return dp[i][j] = 1 + topToButtom(dp, i - 1, j - 1, a, b);
            return dp[i][j] = Math.max(topToButtom(dp, i - 1, j, a, b), topToButtom(dp, i, j - 1, a, b));
        }
    }
}