题目描述

动态规划组成部分一：确定状态

子问题

动态规划组成部分三：初始条件和边界情况

动态规划组成部分四：计算顺序

Java代码实现：

    public int longestCommonSubsequence(String A, String B) {
        int m = A.length();
        int n = B.length();
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        int[][] f = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++)
            f[i][0] = 0;
        for (int j = 0; j <= n; j++)
            f[0][j] = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (a[i - 1] == b[j - 1])
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
        return f[m][n];
    }