/**
1. text1 的子串 和 text2 子串的最长公共子序列一定是text1 和 text2 的最长公共子序列的一部分, 所以可以用动态规划来做
2. 状态定义: f[i][j] 是 1~i 和 1~j 的最长公共子序列长度
    2.1 符合"最优子结构" 和 "无后效性"
3. 状态计算: 以2个串的最后一位i, j划分为4种情况:
    3.1 text1不包含i, text2不包含j: f[i][j] = f[i-1][j-1] 
    3.2 text1包含i,   text2不包含j: f[i][j] = f[i-1][j] + 1
    3.3 text1不包含i, text2包含j:   f[i][j] = f[i][j-1] + 1
    3.4 text1包含i,   text2包含j:   f[i][j] = f[i-1][j-1] + 1

4. 边界: f[~][~] = 0, 
*/

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        int[][] f = new int[n][m];
        for (int i = 0 ; i < n ; i++){
            for (int j = 0; j < m ; j++){
                if (i >= 1 && j >= 1) f[i][j] = f[i-1][j-1];
                if (i >= 1) f[i][j] = Math.max(f[i][j], f[i-1][j]);
                if (j >= 1) f[i][j] = Math.max(f[i][j], f[i][j-1]);
                if (text1.charAt(i) == text2.charAt(j)) f[i][j] = Math.max(f[i][j],(i >= 1 && j >= 1? f[i-1][j-1] : 0) + 1);
            }
        }
        return f[n-1][m-1];
    }
}