漫畫(huà)：最長(zhǎng)公共子序列
-
當(dāng)兩個(gè)字符串 i，j 索引對(duì)應(yīng)的字符相等時(shí)，如下圖示
此時(shí) 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] 的最長(zhǎng)公共子序列即可，即 dp[i-1][j], 同理對(duì)于dp[i][j-1]，即為丟棄 j ，求 str1[0..i] 與 str2[0..j-1] 的最長(zhǎng)公共子序列
既然 dp[i][j] 有可能等于這兩個(gè)值，那么顯然應(yīng)該取這兩者的較大值，?
即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。綜上可知狀態(tài)狀態(tài)方程如下：
?阿寶的想法:
空字符串與任何字符串的最長(zhǎng)公共子序列都為 0，所以 dp[0][i], dp[j][0] 都為 0（i
為 0 到 str1 的長(zhǎng)度， j 為 0 到 str2 的長(zhǎng)度）,如下圖藍(lán)色部分即為 base case。
代碼如下
public?class?Solution?{
????public?static?int?getLCS(char[]?x,?char[]?y)?{
????????// base case，以下 dp 中的每個(gè)元素默認(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è)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
