[導(dǎo)讀]題目： 給定兩個字符串 str1 和 str2，返回這兩個字符串的最長公共子序列的長度。解釋：一個字符串的子序列是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
-
當(dāng)兩個字符串 i，j 索引對應(yīng)的字符相等時，如下圖示
此時 dp[i][j] 值可能為 dp[i-1][j] 或 dp[i][j-1]， dp[i-1][j] 怎么理解，既然 i 與 j 指向的字符不等，那只要丟棄 i 字符，求?str1[0..i-1] 與 str2[0..j] 的最長公共子序列即可，即 dp[i-1][j], 同理對于dp[i][j-1]，即為丟棄 j ，求 str1[0..i] 與 str2[0..j-1] 的最長公共子序列
既然 dp[i][j] 有可能等于這兩個值，那么顯然應(yīng)該取這兩者的較大值，?
即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。綜上可知狀態(tài)狀態(tài)方程如下：
?阿寶的想法:
空字符串與任何字符串的最長公共子序列都為 0，所以 dp[0][i], dp[j][0] 都為 0（i
為 0 到 str1 的長度， j 為 0 到 str2 的長度）,如下圖藍色部分即為 base case。
代碼如下
public?class?Solution?{
????public?static?int?getLCS(char[]?x,?char[]?y)?{
????????// base case，以下 dp 中的每個元素默認(rèn)值都為?0。
????????int?dp[][]?=?new?int[x.length][y.length];
????????for?(int?i?=?1;?i?????????????for?(int?j?=?1;?j?????????????????//?以下邏輯為狀態(tài)轉(zhuǎn)移方程
????????????????if?(x[i]?==?y[j])?{
????????????????????dp[i][j]?=?dp[i-1][j-1]?+?1;
????????????????}?else?{
????????????????????dp[i][j]?=?Math.max(dp[i-1][j],?dp[i][j-1]);
????????????????}
????????????}
????????}
????????return?dp[x.length-1][y.length-1];
????}
????public?static?void?main(String[]?args)?{
????????char[]?x?=??{'?',?'a',?'b',?'c',?'e',?'f',?'g'};
????????char[]?y?=??{'?',?'a',?'c',?'d',?'g'};
????????int?lcs?=?getLCS(x,?y);
????????System.out.printf("lcs?=?"?+?lcs);
????}
}
特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
