题设:
    给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

    这里需要明确子序列的概念: 是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串. 例如： “ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列 。

    示例：
    输入：text1 = “abcde”, text2 = “acef”
    输出：3
    解释：最长公共子序列是 “ace”，它的长度为 3。

    问题分析：

    对于输入的两个字符串是不变的，可变的就是对字符串进行遍历的下标。然后需要考虑的是，对于个问题该如何去尝试，常用的尝试有 从左到右的尝试 和 基于范围的尝试等四种，这里首先考虑从左往右的尝试方式，即从左向右的分别去遍历这两个 字符串。在尝试之前需要先选择模型：

    对于本题的情况明显的只需要选择两个下标作为可变传参就好，所以
    定义

    f(i,j) i∈[0,text1.length), j ∈[0,text2.length)

    代表在输入字符串 text1 , text2 的分别对应你下标i,j 的时候，对应的最长公共子序列的长度
    这样求解的问题就变成了 f(text1.length-1, text2.length-1)

    调用时的传参为: f(text1.length-1,text2.length-1)
    递归调用的边界条件有：
    ① i = 0 , j = 0 : f(i,j) = (text1[0] == text2[0]) ? 1 : 0;
    ② i = 0 , j ∈[1,text2.length) ; f(i,j) = max(f(0,j-1) , text1[0] == text2[j] ? 1 : 0);
    ③ j = 0 , i ∈[1,text1.length) ; f(i,j) = max(f(i-1,0) , text1[i] == text2[0] ? 1 : 0);

    递归调用的依赖关系(情况枚举)为:
    f(i,j) = f(i-1,j-1) ; text1[i] != text2[j] 且 text1[i],text2[j] 并没有增加公共子序列的长度
    f(i,j) = max(f(i-1,j),f(i,j-1)) ; text1[i] != text2[j] 且 text1[i] 或者 text2[j] 增加了公共子序列的长度
    f(i,j) = f(i-1,j-1) + 1 ; text1[i] = text2[j]

    分析到这里，基本上就到了可以实现的程度了，下面看看递归的写法

    递归实现：

    1.     public int longestCommonSubsequence(String text1, String text2) {
    2.         int len1 = text1.length() ,len2=  text2.length();
    3.         return f(text1.toCharArray(),text2.toCharArray(),len1-1,len2-1);
    4.     }
    6.     private int f(char[]ch1 , char[]ch2 , int i , int j){
    7.         if(i == 0 && j == 0){
    8.             return ch1[i] == ch2[j] ? 1 : 0;
    9.         }else if(i == 0){
    10.             return Math.max(f(ch1,ch2,i,j-1) , ch1[i] == ch2[j] ? 1 : 0);
    11.         }else if(j == 0){
    12.             return Math.max(f(ch1,ch2,i-1,j) , ch1[i] == ch2[j] ? 1 : 0);
    13.         }
    14.         // i, j均不为 0的情况
    15.         int p = -1;
    16.         int ret = Math.max(f(ch1,ch2,i-1,j),f(ch1,ch2,i,j-1));
    17.         if(ch1[i] == ch2[j]){
    18.             p = f(ch1,ch2,i-1,j-1) + 1;
    19.         }
    20.         return Math.max(p,ret);
    21.     }

    基本上属于对于问题分析的翻译，代码看着好理解，但是这里面的性能问题就值得担忧了，可以通过画递归树看出，上面实现中存在大量的重复计算问题，对于重复计算我们一般需要加个数组或者其他什么结构将数据存起来(记忆化搜索方式) 以此来减少重复计算。 也可以通过动态规划的方式来改造这类带重复计算的问题。

    动态规划改造：
    把输入 text1 和 text2 分别当二维数组的列和行， 表格dp中dp[i][j] 的位置分别代表 f(i,j) 的取值, 那么我们这时要求的就是 dp[text1.length-1][text2.length-1] ， 以题设中的例子

    text1 = “abcde”, text2 = “ace”

    来看，就有下面的二维表格：
    image.png
    表格的第一行和第一列，我们是可以通过比较其中一个字符串的第一个字符和另个字符串的全部得到，因此可以视为dp表格的初始化数据，剩下的就是求对于任意的 i∈[1,text1.length) 和 j ∈[1,text2.length) dp[i][j]的值。

    由上面的分析，显然dp[i][j] 的取值具有如下的关系：

    dp[i][j] = dp[i-1][j-1] ; text1[i] != text2[j] 且 text1[i],text2[j] 并没有增加公共子序列的长度 dp[i][j]= max(dp[i-1][j],dp[i][j-1] ) ; text1[i] != text2[j] 且 text1[i] 或者 text2[j] 增加了公共子序列的长度 dp[i][j] = dp[i-1][j-1] + 1 ; text1[i] = text2[j]

    这样分析之后，基本上DP的实现思路就明确了。

    动态规划实现：

    1.      public int longestCommonSubsequence(String text1, String text2) {
    2.         int RN = text1.length(), CN = text2.length();
    3.         char[] ch1 = text1.toCharArray(), ch2 = text2.toCharArray();
    4.         int[][] dp = new int[RN][CN];
    5.         // 初始化DP数组
    6.         dp[0][0] = (ch1[0] == ch2[0]) ? 1 : 0;
    7.         for(int j = 1 ; j < CN ; j++){
    8.             dp[0][j] = Math.max(dp[0][j-1], ch1[0] == ch2[j]? 1 : 0);
    9.         }
    10.         for(int i = 1 ; i < RN ; i++){
    11.             dp[i][0] = Math.max(dp[i-1][0] , ch1[i] == ch2[0] ? 1 : 0);
    12.         }
    13.         // 状态转移
    14.         for(int i = 1 ; i < RN ; i++){
    15.             for(int j = 1 ; j < CN ; j++){
    16.                 int temp = Math.max(dp[i-1][j],dp[i][j-1]);
    17.                 int  kk = -1;
    18.                 if(ch1[i] == ch2[j]){
    19.                     kk = dp[i-1][j-1] + 1;
    20.                 }
    21.                 dp[i][j] = Math.max(kk,temp);
    22.             }
    23.         }
    24.         return dp[RN-1][CN-1];
    25.     }