1、最長(zhǎng)公共子序列問題是什么問題？

image.png

2、最長(zhǎng)公共子序列的動(dòng)態(tài)規(guī)劃三步曲？

• 思路啟發(fā)：TMD 也太難了，這怎么想得到
• ①首先是二維數(shù)組，所以定義 dp[i][j]
• ②其次，從后往前面推（或者從前往后推），看看存在什么關(guān)系，從而搞出狀態(tài)轉(zhuǎn)移方程

image.png

3、上述思想的代碼實(shí)現(xiàn)？

image.png

image.png

4、最長(zhǎng)公共子序列-非遞歸實(shí)現(xiàn)？

image.png

5、如果要對(duì)上述代碼進(jìn)行空間優(yōu)化要怎么做？

• 那必須分析 dp[i][j] 的使用過程

image.png

• 可以發(fā)現(xiàn)，dp 的分析，每一行的計(jì)算只依賴于上一行，所以可以使用滾動(dòng)數(shù)組的方式進(jìn)行優(yōu)化。

6、基于上面的 dp 分析，每一行的計(jì)算只依賴于上一行，所以可以用滾動(dòng)數(shù)組的思路進(jìn)行優(yōu)化？

image.png

7、上面是使用了 i <= 1的二維數(shù)組，其實(shí)可以優(yōu)化到直接使用一維數(shù)組？

image.png

8、基于上一步的優(yōu)化完畢，我們可以發(fā)現(xiàn)一維數(shù)組的話，還可以進(jìn)行優(yōu)化，將長(zhǎng)度較短的作為一維數(shù)組，可以進(jìn)一步節(jié)約空間

image.png