2. DP_最长公共子序列

一、题目

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.
Have you met this question in a real interview?
Yes

Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.

**Notice that the subsequence may be discontinuous in these original sequences.

二、解题思路

求『最长』类的题目往往与动态规划有点关系，这里是两个字符串，故应为双序列动态规划。比较基础的题。

以 f[i][j] 表示字符串 A 的前 i 位和字符串 B 的前 j 位的最长公共子序列数目。

• 若 A[i] == B[j], 则分别去掉这两个字符后，原 LCS 数目减一。所以在 A[i] == B[j] 时 LCS 最多只能增加1。即：f[i][j] = f[i-1][j-1]+1。

• 而在 A[i] != B[j] 时，由于A[i] 或者 B[j] 不可能同时出现在最终的 LCS 中，故这个问题可进一步缩小， f[i][j] = max(f[i - 1][j], f[i][j - 1]) .

三、解题代码

public class Solution {  
    /** 
     * @param A, B: Two strings. 
     * @return: The length of longest common subsequence of A and B. 
     */  
    public int longestCommonSubsequence(String A, String B) {  
        if (A == null || A.length() == 0) return 0;  
        if (B == null || B.length() == 0) return 0;  
  
        int lenA = A.length();  
        int lenB = B.length();  
        int[][] lcs = new int[1 + lenA][1 + lenB];  
  
        for (int i = 1; i < 1 + lenA; i++) {  
            for (int j = 1; j < 1 + lenB; j++) {  
                if (A.charAt(i - 1) == B.charAt(j - 1)) {  
                    lcs[i][j] = 1 + lcs[i - 1][j - 1];  
                } else {  
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);  
                }  
            }  
        }  
  
        return lcs[lenA][lenB];  
    }  
}  

下一篇: 3. DP_Lintcode76 最长增长(上升)子序列Longest Increasing Subsequence solution
上一篇: 1. DP_LeetCode114. Distinct Subsequences