此題我的往期文章推薦：

leetCode 1143.最長公共子序列 動態(tài)規(guī)劃 + 滾動數(shù)組-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133689692?spm=1001.2014.3001.5501leetCode 1143.最長公共子序列 一步步思考動態(tài)規(guī)劃 + 優(yōu)化空間復(fù)雜度_呵呵噠(￣▽￣)"的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133702506?spm=1001.2014.3001.5501

?（1）S1 和 S2末尾字符相同時，那就在 S1前 i-1個字符 與 S2前 j-1個字符 的LCS基礎(chǔ)上再加1

?（2）S1 和 S2末尾字符不相同時，兩種選擇方案：

• 把S1的末尾字符拋棄掉，計算在 S1前 i-1個字符 與 S2前 j 個字符?的LCS
• 把S2的末尾字符拋棄掉，計算在 S1前 i個字符 與 S2前 j-1 個字符?的LCS

比較這兩個LCS誰最大，就選最大的LCS為最優(yōu)解?

• ?dp[0][0] 表示?S1 前 0 個字符 與 S2 前 0 個字符的?LCS = 0
• ?dp[i][0] 表示?S1 前 i?個字符 與 S2 前 0 個字符的 LCS = 0
• ?dp[0][j] 表示?S1 前 0 個字符 與 S2 前 j 個字符的 LCS = 0

• S1：A B C B D A B
• S2：B D C A B C

我們可以從這張表格可以得到的信息，S1 與 S2 的?最長公共子序列長度為 4，且最長公共子序列有"BCAB" 和 "BDAB"，如下驗證：

① 最長公共子序列有"BCAB"

• S1：A B C B D A B
• S2：B D C A B C

② 最長公共子序列有"BDAB"

• S1：A B C B D A B
• S2：B D C A B C

偽代碼：

可以在力扣運行的代碼我在這往期文章里已經(jīng)寫了，大家可以移步去看！！！文章鏈接在此文的首行~

參考B站up主邋遢大哥233做的課堂筆記：

[輕松掌握動態(tài)規(guī)劃]5.最長公共子序列 LCS_嗶哩嗶哩_bilibilihttps://www.bilibili.com/video/BV1ey4y1d7oD/?spm_id_from=333.999.0.0&vd_source=a934d7fc6f47698a29dac90a922ba5a3來自up主邋遢大哥233的課堂截圖：