動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃三要素
重疊子問(wèn)題：重復(fù)計(jì)算
最優(yōu)子結(jié)構(gòu)：通過(guò)子問(wèn)題的最值得到原問(wèn)題的最值
-
狀態(tài)轉(zhuǎn)移方程：列出正確的「狀態(tài)轉(zhuǎn)移方程」才能正確地窮舉
#初始化 base case dp[0][0][...] = base #進(jìn)行狀態(tài)轉(zhuǎn)移 for 狀態(tài)1 in 狀態(tài)1的所有取值： for 狀態(tài)2 in 狀態(tài)2的所有取值： for ... dp[狀態(tài)1][狀態(tài)2][...] = 求最值(選擇1，選擇2...)
1、確定 base case。
2、確定「狀態(tài)」，也就是原問(wèn)題和子問(wèn)題中會(huì)變化的變量。
3、確定「選擇」，也就是導(dǎo)致「狀態(tài)」產(chǎn)生變化的行為，即「選擇」。
4、明確 dp 函數(shù)/數(shù)組的定義。
基本動(dòng)態(tài)規(guī)劃：一維
-
509.斐波那契數(shù)（簡(jiǎn)單）
狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i - 1] + dp[i - 2]，可使用狀態(tài)壓縮 -
322.零錢(qián)兌換（中等）
狀態(tài)轉(zhuǎn)移方程：dp[i] = min(dp[i], 1 + dp[i - coin]); -
70. 爬樓梯(簡(jiǎn)單)
狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i-1] + dp[i-2]，可使用狀態(tài)狀態(tài)壓縮 -
198. 打家劫舍(簡(jiǎn)單)
狀態(tài)轉(zhuǎn)移方程：dp[i]=max(nums[i-1]+dp[i-2],dp[i-1])，可使用狀態(tài)壓縮 -
413. 等差數(shù)列劃分(中等)
狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i-1]+1，需要對(duì)dp表求和得到最終的結(jié)果
基本動(dòng)態(tài)規(guī)劃：二維
輸入是二維時(shí)，定義二維的dp數(shù)組
-
64. 最小路徑和(中等)
狀態(tài)轉(zhuǎn)移方程：if(i==0&&j==0) dp[0][0] = grid[0][0]; else if(i==0) dp[i][j] = dp[i][j-1] + grid[i][j]; else if(j==0) dp[i][j] = dp[i-1][j] + grid[i][j]; else dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]; 542. 01 矩陣
兩個(gè)方向的狀態(tài)轉(zhuǎn)移方程：
dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+1);
dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+1);
dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1);
dp[i][j] = Math.min(dp[i][j],dp[i][j+1]+1);
-
221. 最大正方形
狀態(tài)轉(zhuǎn)移方程：
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
maxEdge = Math.max(maxEdge,dp[i][j]);
子序列問(wèn)題
300. 最長(zhǎng)遞增子序列
base case: dp[i] = 1
狀態(tài)轉(zhuǎn)移方程：
for(int j = 0;j < i;j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
354. 俄羅斯套娃信封問(wèn)題
信封嵌套問(wèn)題就需要先按特定的規(guī)則排序，之后就轉(zhuǎn)換為一個(gè) 最長(zhǎng)遞增子序列問(wèn)題。先對(duì)寬度 w 進(jìn)行升序排序，如果遇到 w 相同的情況，則按照高度 h 降序排序。之后把所有的 h 作為一個(gè)數(shù)組，在這個(gè)數(shù)組上計(jì)算 LIS 的長(zhǎng)度就是答案。
1143. 最長(zhǎng)公共子序列
dp數(shù)組定義：dp[i][j]含義是對(duì)于s1[0..i-1]和s2[0..j-1],LCS長(zhǎng)度是dp[i][j]
base case:dp[0][:]和dp[:][0]初始化為0，表示空串
狀態(tài)轉(zhuǎn)移方程：
if(text1.charAt(i-1)==(text2.charAt(j-1)))
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
編輯距離問(wèn)題
72. 編輯距離
狀態(tài)轉(zhuǎn)移方程：相等不變，不等增刪改
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = min(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1);
}
最大子數(shù)組問(wèn)題
53. 最大子序和
dp數(shù)組定義 ：dp[i]表示以nums[i]結(jié)尾的最大子數(shù)組和。
狀態(tài)轉(zhuǎn)移方程：dp[i] = Math.max(dp[i],dp[i-1]+nums[i]);
base case：dp[0] = nums[0];
516. 最長(zhǎng)回文子序列
dp定義比較特殊：在子串s[i...j]中，最長(zhǎng)回文子序列的長(zhǎng)度為dp[i][j]
1312. 讓字符串成為回文串的最少插入次數(shù)
回文串的dp定義基本相同：dp[i][j]表示i-j子串的相應(yīng)值
狀態(tài)轉(zhuǎn)移方程：
if(s.charAt(i)==s.charAt(j))
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
背包問(wèn)題
0-1背包
dp[i][j] 表示前i個(gè)物品，背包容量為j時(shí)，能裝下的最大價(jià)值
base case：dp[0][:] = dp[:][0]=0.表示0個(gè)物品或者0容量，最大價(jià)值為0
狀態(tài)轉(zhuǎn)移方程：
if(num[i-1] > j )
dp[i][j]=dp[i-1][j]
else
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]+vals[i-1]);
子集背包
416. 分割等和子集
先求和得sum，轉(zhuǎn)化為背包問(wèn)題：對(duì)N個(gè)物品，sum/2的容納重量，每個(gè)物品的重量為nums[i]，是否存在一種裝法，可以將背包裝滿？
dp[i][j] 表示 對(duì)容量為j的背包，使用i個(gè)物品可以將其裝滿
base case: dp[:][0]=true：沒(méi)有空間相當(dāng)于裝滿了，dp[0][:]=false：沒(méi)有物品，不可能裝滿
狀態(tài)轉(zhuǎn)移方程：
if(nums[i-1] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
完全背包：物品數(shù)量無(wú)限
518. 零錢(qián)兌換 II
分割類(lèi)型題
數(shù)據(jù)結(jié)構(gòu)
二叉樹(shù)
124. 二叉樹(shù)中的最大路徑和
105. 從前序與中序遍歷序列構(gòu)造二叉樹(shù)
二叉搜索樹(shù)
700. 二叉搜索樹(shù)中的搜索
701. 二叉搜索樹(shù)中的插入操作
98. 驗(yàn)證二叉搜索樹(shù)
450. 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)
99. 恢復(fù)二叉搜索樹(shù)
完全二叉樹(shù)
222. 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
序列化和反序列化二叉樹(shù)
