算法——最长公共子序列（动态规划）

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
leetcode

解题思路：常规的动态规划问题。

1. 首先是状态表示，用一个二维数组，两个维度分别表示两个字符串的长度下标，元素值表示这两个下标范围的最长公共子序列。
2. 然后是状态转移，二层循环遍历两个字符串，如果当前字符相等，则当前值是前一个下标的元素加一；如果不相等，则取两个字符串前一位的最大值。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m = text2.length();
        if(n == 0 || m == 0) return 0;

		// 为了避免特判零的边界问题，全部下标往前移动1
        int[][] f = new int[n + 1][m + 1];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    f[i + 1][j + 1] = f[i][j] + 1;
                } else {
                    f[i + 1][j + 1] = Math.max(f[i + 1][j], f[i][j + 1]);
                }
            }
        }

        return f[n][m];
    }
}