一、動態(tài)規(guī)劃中篇
1、動態(tài)規(guī)劃的新手三步曲是什么？
- ①暴力遞歸（自頂向下，會出現(xiàn)重復(fù)計算子問題）
- ②記憶化搜索（自頂向下，為解決重復(fù)計算子問題）
- ③遞推（自底向上，去除遞歸）
image.png
2、動態(tài)規(guī)劃的常規(guī)步驟，也是三步曲（這應(yīng)該是最重要的專業(yè)概念了）
- ①定義狀態(tài)（狀態(tài)是原問題、子問題的解）：比如定義 dp(i)的含義
- ②設(shè)置初始狀態(tài)（邊界）：比如設(shè)置 dp(0)的值
- ③確定狀態(tài)轉(zhuǎn)移方程：比如確定 dp(i) 和 dp(i-1) 的關(guān)系
- 上述概念結(jié)合
兌換零錢的例子，就理解起來很到位
image.png
image.png
3、可以通過動態(tài)規(guī)劃來解決的問題，通常具備哪 2 個特點？分別是什么含義？
- 最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）：通過求解子問題的最優(yōu)解，可以獲得原問題的最優(yōu)解
- 無后效性：某階段的狀態(tài)一旦確定，則此后過程的演變不再受到此前各狀態(tài)及決策的影響（未來與過去無關(guān)）
image.png
4、借助下面例子理解，什么是無后效性？
- dp(i-1) 對后面的 dp(i) 沒有任何影響
image.png
5、結(jié)合例子理解，什么是有后效性？
- dp(i-1) 的路線選擇，會對 dp(i)的結(jié)果造成影響，就是有后效性
image.png
二、最大連續(xù)子序列和
1、什么是最大連續(xù)子序列和的問題？
- 給定一個長度為 n 的整數(shù)序列，求它的最大連續(xù)子序列和？
- 比如 -2, 1, -3, 4, -1, 2, 1, -5, 4 的最大連續(xù)子序列和是 4 + (-1) + 2 + 1 = 6
2、它的狀態(tài)如何定義？
- 狀態(tài)定義真的很難，如果提高定義的效率呢？
- 總得來說還是得把題目讀透徹了，如何把題目讀透徹呢？
- 像下面的做法，把最優(yōu)解獲得的思路多分析幾遍，看看有哪幾種思路？
- 然后分析 i 從 0 到 8 的情況，大概率就能找到規(guī)律了。
- 總結(jié)：“走進題目，熟讀題目”
image.png
3、狀態(tài)定義好了，如何找狀態(tài)轉(zhuǎn)移方程和初始化？
image.png
4、有了動態(tài)規(guī)劃的三要素，如何編寫遞推代碼呢？
image.png
5、仔細(xì)觀察上面的代碼執(zhí)行流程，是否存在優(yōu)化點？
- 可以從以下兩個角度入手找優(yōu)化：
- ①分配了空間，但是后面都沒用到了（從空間復(fù)雜度優(yōu)化）
- ②能不能再循環(huán)的時候，順便把事情做了（從時間復(fù)雜度優(yōu)化）
- 分析上述代碼：
- dp(6) 僅僅依賴于 dp(5)，dp(7)僅僅依賴于dp(6)，dp[i]僅僅依賴于 dp[i-1]
- 然而我們存了 dp[0]、dp[1]、dp[2]......dp(n) 的所有數(shù)據(jù)，所以我們的空間有點浪費的，是存在優(yōu)化點的。
image.png
三、最長上升子序列
1、題意準(zhǔn)確理解：子序列要求是連續(xù)的嗎？
- 子序列不需要連續(xù)
2、什么是經(jīng)典的：最長上升子序列問題？
image.png
- 拿到一道算法題，首先最重要的是理解題意
- 理解題意可以通過帶入幾個最優(yōu)解的情況，這樣比較容易深入理解題意。
2、動態(tài)規(guī)劃 - 狀態(tài)定義
image.png
3、動態(tài)規(guī)劃 - 狀態(tài)轉(zhuǎn)換方程的定義
image.png
4、動態(tài)規(guī)劃 - 代碼的實現(xiàn)
image.png
5、使用牌堆和二分搜索法，是另一種思路（這種思路太難想，目前作為了解吧）
image.png
image.png
image.png
