前言
遇到了用動態(tài)規(guī)劃來求解最長公共子序列問題，算法這塊兒比較薄弱，便想著在網(wǎng)上找現(xiàn)成的思路和代碼，也算拾人牙慧，但有一點沒想到，都已經(jīng)22年了，關于LCS問題網(wǎng)上給出的答案如此一言難盡……，只有零散幾篇對于新手來說比較友好，但也僅僅這樣，好在自己花了點時間，勉強領悟了一番，寫以成文，以便來時溫故。
動態(tài)規(guī)劃基本思想及要點
這塊兒是看吳師兄學算法(公眾號)文章摘錄的
基本思想
動態(tài)規(guī)劃算法與分治法類似，其基本思想就是將待求解問題分解成若干子問題，先求解子問題，然后從這些問題的解得到原問題的解。與分治法不同的是，適合動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是相互獨立的。
在用分治法求解時，有些子問題被重復結算了很多次，如果我們能夠保存已解決子問題的答案，在需要時找出已求得答案，這樣就可以避免大量重復計算，可以用一個表來記錄所有已解決子問題的答案，不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中，而這就是動態(tài)規(guī)劃的思想。
小結
- 將待求解問題分成若干子問題，先求子問題，然后從這些子問題的解得到原問題的解
- 經(jīng)分解得到的子問題往往不是相互獨立的
- 保存已解決子問題的答案，避免重復計算
要點
如何判定一個問題是否可以用動態(tài)規(guī)劃來解決，就需要掌握動態(tài)規(guī)劃的兩個基本要素，最優(yōu)子結構性質和重疊子問題性質
最優(yōu)子結構性質
當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質提供了該問題可用動態(tài)規(guī)劃求解的重要線索。
例如，最短路徑問題有如下最優(yōu)子結構:
結點x是從源結點u到目標結點v的最短路徑上的節(jié)點，則源結點u到目標結點v的最短路徑7就等于從源結點u到結點x的最短路徑5加上從結點x到目標結點v的最短路徑2的和。源結點u到目標結點v的最短路徑就是要求解的最優(yōu)解，源結點u到結點x的最短路徑和從結點x到目標結點v的最短路徑均為子問題的最優(yōu)解，而問題的最優(yōu)解包含了其子問題的最優(yōu)解，則該問題具有最優(yōu)子結構性質。
但最長路徑問題就不具有最優(yōu)子結構性質，注意這里的最長路徑指的是從兩個結點間的最長簡單路徑(即不存在環(huán)的路徑)
從結點u到結點v有兩條最長，分別為u——> s ——> v和u ——> t ——> v，但與最短路徑問題不同，這些最長路徑不具有最優(yōu)子結構性質，比如，從結點u到結點v有兩條最長路徑u ——> s ——> v并不等于從u到s的最長路徑u ——> t ——> v ——> s與從s到v的最長路徑s ——> u ——> t ——> v的加和。
重疊子問題性質
簡單講就是子問題的解會被重復調用
LCS問題分析
字串與子序列
有圖有真相
一個長度為n的序列，其子序列個數(shù)為2n-1，所以解決LCS問題最好不使用暴力搜索方法
分解
最長公共子序列問題分解成子問題根據(jù)已造輪子可知，設A=“a0、a1、……、am-1”，B=“b0、b1、……、bn-1”，Z=“z0、z1、……、zk-1”為它們最長公共子序列，不難證明有如下性質:
1). 如果am-1 = bn-1，則zk-1 = am-1=bn-1，簡單講就是A和B最后一個字符相等，那么這個字符肯定為最長公共子序列中的最后一個字符，于是就有“z0、z1、……、zk-2”是“a0、a1、……、am-2”和“b0、b1、……、bn-2”的一個最長公共子序列
2). 如果am-1!=bn-1，則若zk-1!=am-1，那么“z0、z1、……、zk-1”是“a0、a1、……、am-2”和“b0、b1、……、bn-1”的一個最長公共子序列
3). 如果am-1!=bn-1，則若zk-1!=bn-1，那么“z0、z1、……、zk-1”是“a0、a1、……、am-1”和“b0、b1、……、bn-2”的一個最長公共子序列
由此可以獲得遞推公式
dp數(shù)組推導(圖解)
dp數(shù)組用于記錄LCS長度，下面根據(jù)遞歸公式一行行進行推導
簡單演示下填表過程
通過遞推公式進行LCS長度推導這個過程，可以知道dp[i][j]是從三個方向推出的，分別是左上，向左，向上
構造LCS(回溯)
得到dp數(shù)組后，為了得到LCS需要從dp[7][6]倒推出兩序列共同元素，倒退有三種方向回溯
第一種結果
第二種結果
第三種結果
也就是有
回溯方向以向左回溯為先
代碼實現(xiàn)
下面的代碼為dp數(shù)組及回溯方向的實現(xiàn)(向左回溯為主)
package operation.dp;
public class LCSLD {
public static void LCS(int[][] dir, int [][] dp,String s1,String s2){
for(int i = 1;i <= s1.length();i++){
char c1 = s1.charAt(i - 1);
for(int j = 1;j <= s2.length();j++){
char c2 = s2.charAt(j - 1);
//開始列出狀態(tài)方程
if (c1 == c2){
dp[i][j] = dp[i-1][j-1]+1;
dir[i][j] = 1; //來源左上方
}else{
if (dp[i][j-1] >= dp[i-1][j]){
dp[i][j] = dp[i][j-1];
dir[i][j] = 2; //來源左方
}
else{
dp[i][j] = dp[i-1][j];
dir[i][j] = 3; //來源上方
}
}
}
}
}
public static void LCSD(int [][] dir, int i, int j, String s1){
if(i== 0 || j == 0) {
return;
}
if(dir[i][j] == 1){
LCSD(dir,i - 1,j - 1,s1);
System.out.print(s1.charAt(i - 1));
}else{
if (dir[i][j] == 2)
LCSD(dir,i,j - 1,s1);
else
LCSD(dir,i - 1,j,s1);
}
}
}
下面的代碼為dp數(shù)組及回溯方向的實現(xiàn)(向上回溯為主)
package operation.dp;
public class LCSFD {
public static void LCS(int[][] dir,int [][] dp,String s1,String s2){
for(int i = 1;i <= s1.length();i++){
char c1 = s1.charAt(i - 1);
for(int j = 1;j <= s2.length();j++){
char c2 = s2.charAt(j - 1);
if (c1 == c2){
dp[i][j] = dp[i-1][j-1]+1;
dir[i][j] = 1; //來源左上方
}else{
if(dp[i-1][j] >= dp[i][j-1]){
dp[i][j] = dp[i-1][j];
dir[i][j] = 2; //來源上方
}else{
dp[i][j] = dp[i][j-1];
dir[i][j] = 3; //來源左方
}
}
}
}
}
public static void LCSD(int [][] dir,int i,int j,String s1){
if(i == 0 || j ==0){
return;
}
if(dir[i][j] == 1){
LCSD(dir,i - 1,j - 1,s1);
System.out.print(s1.charAt(i - 1));
}else{
if(dir[i][j] == 2)
LCSD(dir,i - 1,j,s1);
else
LCSD(dir,i,j - 1,s1);
}
}
}
下面的代碼為主程序代碼
package operation.dp;
public class MainApp {
public static void main(String[] args) {
String s1 = "abcbdab";
String s2 = "bdcaba";
//先對dp數(shù)組做初始化操作
//Java中數(shù)組靜態(tài)初始化在編譯時就已完成，而動態(tài)初始化在運行時才完成，
//且動態(tài)初始化的初始值都為0
int [][] dp = new int[s1.length()+1][s2.length()+1]; //i+1行j+1列
int [][] dir = new int[s1.length()+1][s2.length()+1];
int [][] dp1 = new int[s1.length()+1][s2.length()+1]; //i+1行j+1列
int [][] dir1 = new int[s1.length()+1][s2.length()+1];
//開始時間
long stime = System.currentTimeMillis();
//以向左回溯為先
LCSLD.LCS(dir,dp,s1,s2);
System.out.println("dp數(shù)組如下:");
for(int i = 0;i <= s1.length();i++){
for(int j = 0;j <= s2.length();j++){
System.out.printf("%5d",dp[i][j]);
}
System.out.println();
}
System.out.println("回溯數(shù)組如下:");
for(int i = 0;i <= s1.length();i++){
for(int j = 0;j <= s2.length();j++){
System.out.printf("%5d",dir[i][j]);
}
System.out.println();
}
System.out.print("最長公共子序列為:");
LCSLD.LCSD(dir,s1.length(),s2.length(),s1);
System.out.println();
//以向上回溯為先
LCSFD.LCS(dir1,dp1,s1,s2);
System.out.println("回溯數(shù)組如下:");
for(int i = 0;i <= s1.length();i++){
for(int j = 0;j <= s2.length();j++){
System.out.printf("%5d",dir1[i][j]);
}
System.out.println();
}
System.out.print("最長公共子序列為:");
LCSFD.LCSD(dir1,s1.length(),s2.length(),s1);
System.out.println();
//結束時間
long etime = System.currentTimeMillis();
System.out.printf("執(zhí)行時長: %d 毫秒",(etime - stime));
}
}
主程序運行結果如下
待解決問題
經(jīng)過上述努力，發(fā)現(xiàn)LCS回溯的方向可以說是一根筋兒，這樣就導致結果不全，以上述例子來說，LCS總共有三個，結果只能輸出兩個，暫時只能到這兒了，以后看看有沒有機會實現(xiàn)
參考
主要是看了四篇文章有所啟迪，一篇CSDN上的、一篇博客園上的、一篇公眾號上的、一篇個人博客上的文章來源：http://www.zghlxwxcb.cn/news/detail-400011.html
小結
好的算法講解真的很重要，可以事半功倍，就目前接觸而言，代碼隨想錄的算法講解很不錯(對新手友好且免費)，其他成體系成專欄的講解(暫時沒有發(fā)現(xiàn)，可能都在自己的一畝三分地下)希望多多涌現(xiàn)，這樣后來者學習算法就可以站在前人肩上前行了，也許時代造就了現(xiàn)在的社會氛圍較為著急，很難靜下心來公益的分享知識，所以不能一味歸咎于個人(機構)老是搞錢，等中國的科技素養(yǎng)追趕上了中國的科技水平，那時候也許環(huán)境不會這么苛責，現(xiàn)在如果每個人認真發(fā)一份光，其實也可以燎原，不需要等待那天到來，說通透點就是，我花個一天時間把這個問題弄通透，然后分享出來，你花一天時間把那個問題弄通透分享出來，那么對于第三方來說在這兩個問題就可以少走較小彎路了，當然，這說的也可能扯淡，不好把握全局，不好定性脈絡，認知差信息差總是提醒著我，多走幾步，再回頭觀望那時的想法是否正確文章來源地址http://www.zghlxwxcb.cn/news/detail-400011.html
到了這里，關于(Java) 算法——動態(tài)規(guī)劃 最長公共子序列 圖解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
