动态规划求最长公共子序列

这是一道很经典的动态规划题目。

求解步骤

• 确定状态与选择 状态是LCS的长度。
  如果S[i] == T[j]，LCS的长度 + 1; 当不等时，必须选择一个存在于LCS中的字符，但是我们当前肯 定不知道哪个是属于LCS里的字符，所以就拿LCS的长度来比较。这里就有两个选择。
• 明确dp的含义，定义base case
  dp[i][j]指的是S[0...i-1]和T[0...j-1]中LCS的长度，因为数组的索引是从0开始的，而我们的dp数组是从1开始的，所以base case将dp[0][...]和dp[...][0]置为0。
• 找出状态方程
  从我们的选择中，可以推出状态转移方程：
  • if(S[i] == T[j]) dp[i+1][j+1] = dp[i-1][j-1] + 1;
  • if(S[i] != T[j]) dp[i+1][j+1] = Math.max(dp[i-1][j], dp[i][j-1]);

动态规划的解法

• 递归实现 dp函数 （优化： 备忘录）
• 递推实现 dp数组

递归实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        int[][] memory = new int[len1+1][len2+1];
        for(int i = 0; i <= len1; i++){
            Arrays.fill(memory[i], -1);
        }
        return dp(text1, text2, memory, len1, len2);
    }

    public int dp(String text1, String text2, int[][] memory, int i, int j){
        if(i == 0 || j == 0)
            return 0;
        if(memory[i][j] != -1)
            return memory[i][j];
        if(text1.charAt(i-1) == text2.charAt(j-1)){
            memory[i][j] =dp(text1, text2, memory, i-1, j-1) + 1;
        }else{
            memory[i][j] = Math.max(dp(text1, text2, memory, i-1, j), dp(text1, text2, memory, i, j-1));
        }
        return memory[i][j];
    }
}

也可以从数组左侧开始。

递推实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();

        int[][] dp = new int[len1+1][len2+1];
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; 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][j-1], dp[i-1][j]);
            }
        }
        return dp[len1][len2];
    }
}