問題描述

最長公共子序列(Longest Common Subsequence，LCS)即求兩個序列最長的公共子序列(可以不連續(xù))。比如3 2 1 4 5和1 2 3 4 5兩個序列，最長公共子序列為2 4 5 長度為3。解決這個問題必然要使用動態(tài)規(guī)劃。既然要用到動態(tài)規(guī)劃，就要知道狀態(tài)轉(zhuǎn)移方程。我們令L[i][j] 表示序列 A 和序列 B 的最長公共子序列的長度，則狀態(tài)轉(zhuǎn)移方程如下：
若a[i]=b[j]， 則 L[i][j]=L[i-1][j-1] +1
若a[i]!=b[j]， 則 L[i][j]=max (L[i][j-1]，L[i-1][j]）
即：相同的取左上加1,不同取上和左中的最大值

package com.algorithm;
/*** long common Subseq*/
public class LCS {public static void main(String[] args) {char[] seq1 = new char[]{'a','b','d','c','b','a','b'};char[] seq2 = new char[]{'b','d','c','b','a','b','b'};int[][] dp = new int[seq1.length + 1][seq2.length + 1];//存儲兩個序列當(dāng)前i和j的公共序列長度，多存儲一位是空字符，默認(rèn)都市0//初始化for (int i = 0; i < seq1.length + 1; i++) {dp[i][0] = 0;}for (int j = 0; j < seq2.length + 1; j++) {dp[0][j] = 0;}//計算dp,相同的取左上加1,不同取上和左中的最大值for(int i = 1; i < seq1.length; i++) {for(int j = 1; j<seq2.length; j++) {if(seq1[i] == seq2[j]) {dp[i][j] = dp[i-1][j-1]+1; //左上加1} else {dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]); //上和左中的最大值}}}//獲取最長公共子序列長度，也就是dp中最大的那個值int max = 0;for(int i = 1; i < dp.length; i++) {for (int j = 1; j < dp.length; j++) {max = Math.max(max, dp[i][j]);}}System.out.println("long common seq size:"+max);}
}

從右下角開始，如果有dp[i][j]==dp[i-1][j-1]+1則往左上走一格。得到整個子序列的求解過程。b,c,b,a,b