51Nod-1006 最长公共子序列 LCS

Question

就是输入两个字符串 str1 、 str2 ，输出任意一个最长公共子序列。

解析

dp[i][j] 代表的是 : 必须以 str1[i] 、 str2[j] 结尾的最长公共子序列， dp[i][j] 来源:

• 可能是 dp[i-1][j] ，代表 str1[0~i-1] 与 str2[0~j] 的最长公共子序列。
• 可能是 dp[i][j-1] ，代表 str1[0~i] 与 str2[0~j-1] 的最长公共子序列。
• 如果 str1[i] == str2[j] ，还可能是 dp[i-1][j-1] + 1 。

这三种情况中取最大值。

构造结果的过程（利用 dp 数组即可)

• 从矩阵的右下角开始，有三种移动方式: 向上、向左、向左上。
• 如果 dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1] ，说明之前在计算 dp[i][j] 的时候，一定是选择了 dp[i-1][j-1]+1 ，所以可以确定 str1[i] = str2[j] ，并且这个字符一定输入最长公共子序列，把这个字符放进结果字符串，然后向左上方移动；
• 如果 dp[i][j] == dp[i-1][j] ，说明之前计算 dp[i][j] 的时候， dp[i-1][j-1]+1 不是必须的选择，向 上方移动即可；
• 如果 dp[i][j] == dp[i][j-1] ，向 左方移动即可；
• 如果 dp[i][j] 同时等于 dp[i-1][j] 和 dp[i][j-1] ，向上向左都可以，选择一个即可，不会错过必须选择的字符；

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    /** dp[i][j]代表的是 str[0..i]与 str[0...j]的最长公共子序列*/
    public static int[][] getDp(char[] sa,char[] sb){
        int[][] dp = new int[sa.length][sb.length];
        dp[0][0] = sa[0] == sb[0] ? 1 : 0;
        for(int i = 1; i < sa.length; i++)  // 一旦 dp[i][0]被设置成 1,则 dp[i~N-1][0]都为 1
            dp[i][0] = Math.max(dp[i-1][0], sa[i] == sb[0] ? 1 : 0);
        for(int j = 1; j < sb.length; j++)
            dp[0][j] = Math.max(dp[0][j-1], sb[j] == sa[0] ? 1 : 0);
        for(int i = 1; i < sa.length; i++){
            for(int j = 1; j < sb.length; j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                if(sa[i] == sb[j]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1);
                }
            }
        }
        return dp;
    }

    /*** 求出最长公共子序列*/
    public static String getLCS(String sa, String sb, int[][] dp){
        if(sa == null || sb == null || sa.equals("") || sb.equals(""))
            return "";
        char[] chs1 = sa.toCharArray();
        char[] chs2 = sb.toCharArray();
        int i = chs1.length - 1;  
        int j = chs2.length - 1;
        char[] res = new char[dp[i][j]]; //生成答案的数组
        int index = dp[i][j] - 1;
        while(index >= 0){
            if(i > 0 && dp[i][j] == dp[i-1][j]){
                i--;
            }else if(j > 0 && dp[i][j] == dp[i][j-1]){
                j--;
            }else { // dp[i][j] = dp[i-1][j-1]+1
                res[index--] = chs1[i];
                i--;
                j--;
            }
        }
        return String.valueOf(res);
    }


    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        String sa = cin.next();
        String sb = cin.next();
        int[][] dp = getDp(sa.toCharArray(), sb.toCharArray());
//        System.out.println(dp[sa.length()-1][sb.length()-1]); //length of lcs
        System.out.println(getLCS(sa, sb, dp));
    }
}

题目链接

http://www.51nod.com/Challenge/Problem.html#!#problemId=1006