我讀過文章，找到兩個給出字符串之間最長的共同點。找到最長的共同序列
我才知道的算法代碼如下：
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++){
if(i==0 || j==0) dd[i][j]=0;
else if(a[i-1]==b[j-1])
dd[i][j] = 1 + dd[i-1][j-1];
else{
dd[i][j] = Math.max(dd[i-1][j], dd[i][j-1]);
}
}
我不幹明白這一點，但我不明白它是如何工作的，即是什麼正常工作它的證明。爲什麼這個東西的工作，請幫助我理解算法
讓利，
str1 = "bcd"
str2 = "dabc"
這裏n=3和m=4
The outer loop is for str1 and inner loop is for str2
這裏是dd陣列的第一外觀：
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
"dabc" with 'b'現在當'b'與"dabc"比較時，我們看到在第4次迭代中將會有一個匹配，因此數組值將相對於角當前位置的r值。當前位置是[1][3]。作爲拐角([0][2])值爲0，電流值將是1：
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
在迭代結束時的陣列將是這樣的：
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 0, 0
0, 0, 0, 0, 0
的[1][4]位置值改變，因爲如果一個字符的str2與str1的當前字符不匹配，則當前位置的值將是當前位置的上和左位置之間的最大值。這裏的最大值是1。
現在檢查自己，如果str1="b"最大的比賽將是1，這是我們計算在每個迭代的str1每個條目的最大匹配。
"dabc" with 'c'現在在第五次迭代將有一個匹配，所以陣列值將是相對於當前位置的角落值而改變。當前位置是[2][4]。由於角落([1][3])價值1，電流值將是2：
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 1, 2
0, 0, 0, 0, 0
現在檢查自己，如果str1="bc"最大的比賽將是2，這是我們計算在每個迭代的str1每個條目的最大匹配。
在迭代結束時的陣列將是這樣的：
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 1, 2
0, 0, 0, 0, 0
"dabc" with 'd'現在在第二次迭代時會有一個匹配，所以數組值將相對於當前位置的角點值進行更改。當前位置是[3][1]。作爲拐角([2][0])值爲0，電流值將是1：將發生
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 2
0, 1, 0, 0, 0
沒有進一步的匹配。
在迭代的陣列將是這樣的端部：
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 1, 2
0, 1, 1, 1, 2
所以這兩個串的LCS是dd[3][4] = 2。
希望你明白這一點。你也可以從here得到幫助
注意：這裏我只描述了匹配情況。如果str2的一個字符與str1的當前字符不匹配，則當前位置的值將是當前位置的上部位置和左側位置之間的最大值。自己嘗試一下，你就會明白爲什麼我們做這個:)
您是否嘗試過閱讀[Wikipedia文章]很好的解釋（http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution）？ – amit