45.?跳躍游戲 II：

這題可以用貪心，也可以用dp。dp做的話，dp 狀態(tài)定義為到達(dá)某個位置所需的最小步數(shù)，dp[i] = min(dp[i - 1], dp[i - 2],...,dp[j + 1],dp[j]) + 1，dp[i - 1] >= dp[i - 2] >= ... >= dp[j + 1] >= dp[j]，所以有dp[i] = dp[j] + 1 (0<=j <i)，j是最早可以到達(dá)i的點(diǎn)。

70. 爬樓梯：

dp指爬當(dāng)前階數(shù)的方法數(shù)。初始化dp[1]=1,dp[2]=2，從3開始循環(huán)。

746. 使用最小花費(fèi)爬樓梯：

這題的dp有多種寫法。其中一種是，理解dp為到達(dá)當(dāng)前階要花費(fèi)的最小cost。初始化dp[0]=0;dp[1]=0。從2開始循環(huán)dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])，最后的答案是dp[cost.size()]，因?yàn)檫@題的意思是到達(dá)頂，所以是cost.size()。

62. 不同路徑：

經(jīng)典dp，使用二維數(shù)組，初始化兩條邊界為1。dp[i][j]=dp[i-1][j]+dp[i][j-1]。

63. 不同路徑 II：

這題和62是一樣的思路，只是在初始化時如果遇到了障礙，就要break，障礙后面的一行或者一列都是0。在循環(huán)時，如果遇到障礙就跳過。

343. 整數(shù)拆分：

這題一開始一直糾結(jié)于dp[i]=max(dp[i],dp[j]*(i-j))，dp指當(dāng)前的最大乘積，但是這樣寫一直出錯，后來看了題解才知道，dp[j]*(i-j)是j有拆分，但如果j*(i-j)，j不拆分時乘積更大呢？所以正確的狀態(tài)轉(zhuǎn)移方程是dp[i]=max(dp[i],max(dp[j]*(i-j),j*(i-j)))。

96. 不同的二叉搜索樹：

這題挺難的。dp代表當(dāng)前的二叉搜索樹的種數(shù)，dp[0]等于1，空樹也是一顆樹。兩層循環(huán)，dp[i]+=dp[j-1]*dp[i-j]，外循環(huán)i，表示當(dāng)前有多少節(jié)點(diǎn)。內(nèi)循環(huán)j，從1到i，表示當(dāng)前j為該樹的根節(jié)點(diǎn)，j-1為左子樹，i-j為右子樹。