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

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出最长的子序列，如果有多个，随意输出1个。

abcicba
abdkscab

abca

思路：很经典的动态规划题目了，我就不用多说了吧

code：AC

import java.util.Scanner;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        String strA = s.next();
        String strB = s.next();
        char[] chA = strA.toCharArray();
        char[] chB = strB.toCharArray();
        int[][] dp = new int[chA.length][chB.length];
        dp[0][0] = chA[0]==chB[0] ? 1 : 0;
        for(int i=1; i<chB.length; ++i)
        dp[0][i] = chA[0]==chB[i] ? 1 : dp[0][i-1];
        for(int i=1; i<chA.length; ++i)
        dp[i][0] = chA[i]==chB[0] ? 1 : dp[i-1][0];
        for(int i=1; i<chA.length; ++i)
         for(int j=1; j<chB.length; ++j){
             if(chA[i] == chB[j] )
                dp[i][j] = dp[i-1][j-1]+1;
              else
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
         }
         int index = dp[chA.length-1][chB.length-1];
        char[] arr = new char[index];
        int i = chA.length-1;
        int j = chB.length-1;
        while(i>-1 && j>-1){
            if(chA[i] == chB[j]){
                arr[--index] = chA[i];
                --i;
                --j;
            }else if(i-1>-1 && dp[i-1][j] == dp[i][j] ){
                --i;
            }else{
                --j;
            }
        }
        for(int k=0; k<arr.length; ++k)
         out.print(arr[k]);
         out.flush();
    }
}