DP：最长公共子序列Ⅰ

文章目录

DP：最长公共子序列Ⅰ
- - 问题
  - 思路
  - 代码

问题

思路

我们先从最简单的情况入手，设两个字符串为A，B，如果只看两个串的前1个字符，那么如果A[1]等于B[1]，最长公共子序列为1；如果A[1]不等于B[1]，最长公共子序列为0。如果只看前2个字符，如果A[2]等于B[2]，最长公共子序列长度是否等于之前只看前1个字符时的答案+1呢？一个公共子序列一定包含在从第一个字符开始的某个连续序列中，而不同连续序列以不同位置的字符结尾，如果用DP[i]表示两个串前i个字符以第i个字符结尾的最长公共子序列的长度，那么有DP[i]=max{DP[j],j=1~i-1}+(A[i]==B[i])吗？实际上我们不能用这个状态转移方程解题，使用该方程的前提是：两个字符串中连续序列以同一位置i的字符结尾，也就是所判断的两个连续序列是位置对应长度相同的，但题目中并没有要求这一点，公共子序列可以出现在两个字符串的不同连续序列中，再来看看最开始的例子，我们并没有考虑到A[2] = B[1] 或 B[2] = A[1]的情况，也就是说，使用一维dp数组表达不出所有的状态。
为了表示公共子序列处于两个字符串长度不同的连续序列中，我们需要用二维dp数组来表示所有的状态。我们用DP[ i ] [ j ]表示A[1 ~ i] 与 B[1 ~ j]的最长公共子序列的长度，若A[i]==B[j]，则DP[i] [j]由DP[i – 1] [j – 1] + 1转移得到，若不等，则DP[i – 1] [j – 1]由Max(DP[i – 1][j]，DP[i][j – 1])转移得到，注意不等的情况并不是继承DP[i – 1] [j – 1]，因为A[i]虽不等于B[j]，但A[i]可能与B[1 ~ j – 1]包含的子序列中最后一个元素相等，同理，B[j]可能与A[1 ~ i – 1]包含的子序列中最后一个元素相等。
所以状态转移方程为：

初始状态DP[0][0]表示两个空串的最长公共子序列，即为0。

代码

import java.util.*;

public class Main {
    static int[][] dp = new int[1005][1005];
    public static void main(String[] args) {
        StringBuilder str1 = new StringBuilder();
        StringBuilder str2 = new StringBuilder();
        int i, j, ans;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            ans = 0;
            str1.delete(0, str1.length());
            str1.append(scanner.next());
            str2.delete(0, str2.length());
            str2.append(scanner.next());
            dp[0][0] = 0;
            for (i = 1;i <= str1.length();i++) {
                for (j = 1;j <= str2.length();j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                    ans = Math.max(ans, dp[i][j]);
                }
            }
            System.out.println(ans);
        }
    }
}