Longest Common Subsequence

DP入门题，状态方程如下

if A[i] == B[j]
    dp[i][j] = dp[i - 1][j - 1] + 1
else
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

第一种情况是A,B两当前字符相等，则至少他们有一个长度的公共子序列，我们只需要找更小规模的答案即可

第二种情况是A,B两当前字符不等，则只能选择一个字符串往回退再对比

class LCS:
    def findLCS(self, A, n, B, m):
        # write code here
        dp = [[0] * (m + 1) for _ in xrange(n + 1)]

        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[n][m]

Java版本

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        // write code here
        char[] stringA = A.toCharArray();
        char[] stringB = B.toCharArray();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (stringA[i - 1] == stringB[j - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][m];
    }
}

这里是没经过空间优化的算法，空间优化的方法有点问题，需要再研究