算法思想之动态规划(四)——最长公共子序列问题

前言

今天我们继续讨论经典的动态规划问题之最长公共子序列问题。

找零钱问题

问题描述

给定两个字符串str1和str2，返回两个字符串的最长公共子序列的长度。例如，str1="1A2C3”，str2="B1D23”，”123"是最长公共子序列，那么两字符串的最长公共子序列的长度为3。

问题分析

假设两字符串str1和str2的长度分别为n和m。对于这类问题，我们一般可以构建一个大小的矩阵dp，其中代表的是str1中前个字符串与str2中前个字符串的最长公共子序列的长度。
首先，我们需要初始化第0行和第0列的的值，可以通过比较两字符是否相等即可，相等置1，不相等置0，要注意的是一旦在某一位置两字符相等，则该位置后直接置1，代表该位置后的字符串最长的公共子序列为1。对于问题描述中的例子来说，str1中的第1个字符"1"与str2中第1个字符“B”不等，代表"1"与"B"的公共子序列长度为0，即；而str1的第1个字符"1"与与str2中第2个字符"1"相等，代表"1"与"B1"的最长公共子序列为1，即；显然，"1"与"B1"、"B1D"、"B1D2"、"B1D23"的最长公共子序列均为1，即。
接下来，我们就需要从左到右，由上至下依次计算。对于，。我们可以列举出所有可能的取值：
(1) 如果，那么最长公共子序列的长度为前个子字符串与前个子字符串的最长公共子序列长度，即。

(2) 如果，那么最长公共子序列的长度有可能为：

• 前个子字符串与前个子字符串的最长公共子序列长度，即；
• 前个子字符串与前个子字符串的最长公共子序列长度，即；

在二者之间取较大的那一个即可，即。

代码实现

通过问题分析，可以很容易得用代码实现，下面给出算法的java实现。

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        return core(A, n, B, m);
    }

    public int core(String A, int n, String B, int m) {
        if (n == 0 || m == 0) {
            return 0;
        }

        int[][] dp = new int[n][m];
        // 初始化第0行
        for (int i = 0; i < m; i++) {
            if (A.charAt(0) == B.charAt(i)) {
                for (int j = i; j < m; j++) {
                    dp[0][j] = 1;
                }
                break;
            } else {
                dp[0][i] = 0;
            }
        }

        // 初始化第0列
        for (int i = 0; i < n; i++) {
            if (A.charAt(i) == B.charAt(0)) {
                for (int j = i; j < n; j++) {
                    dp[j][0] = 1;
                }
                break;
            } else {
                dp[i][0] = 0;
            }
        }

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

        return dp[n - 1][m - 1];
    }

    public static void main(String[] args) {
        LCS lcs = new LCS();
        String A = "1A2C3";
        int n = A.length();
        String B = "B1D23";
        int m = B.length();
        int res = lcs.findLCS(A, n, B, m);
        System.out.println(res);
    }
}

其他经典问题

• 算法思想之动态规划(二)——最小路径和问题
• 算法思想之动态规划(三)——找零钱问题
• 算法思想之动态规划(五)——最小编辑距离问题
• 最长上升子序列问题
• 背包问题

未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。