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

2019-06-01 本文已影响0人复旦猿

前言

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

找零钱问题

问题描述

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

问题分析

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

(2) 如果 $str1[i] \neq str2[j]$ ，那么最长公共子序列的长度有可能为：

前 $i-1$ 个子字符串与前 $j$ 个子字符串的最长公共子序列长度，即 $dp[i-1][j]$ ；
前 $i$ 个子字符串与前 $j-1$ 个子字符串的最长公共子序列长度，即 $dp[i][j-1]$ ；

在二者之间取较大的那一个即可，即 $dp[i][j] = max \{ dp[i-1][j], dp[i][j-1] \}$ 。

代码实现

通过问题分析，可以很容易得用代码实现，下面给出算法的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);
    }
}

其他经典问题

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

写在最后

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