62.不同路徑

機(jī)器人從(0 , 0) 位置出發(fā)，到(m - 1, n - 1)終點(diǎn)。

動(dòng)規(guī)五部曲

1、確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

2、確定遞推公式
想要求dp[i][j]，只能有兩個(gè)方向來推導(dǎo)出來，即dp[i - 1][j] 和 dp[i][j - 1]。dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因?yàn)閐p[i][j]只有這兩個(gè)方向過來。

3、dp數(shù)組的初始化
首先dp[i][0]一定都是1，因?yàn)閺?0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理。

4、確定遍歷順序
dp[i][j]都是從其上方和左方推導(dǎo)而來，那么從左到右一層一層遍歷就可以了。這樣就可以保證推導(dǎo)dp[i][j]的時(shí)候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值的。

5、舉例推導(dǎo)dp數(shù)組

代碼如下：

class Solution {public int uniquePaths(int m, int n) {int[][] dp=new int[m][n];for(int i=0;i<m;i++) dp[i][0]=1;for(int i=0;i<n;i++) dp[0][i]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}

63. 不同路徑 II

思路：這個(gè)題目和上一題的區(qū)別在于增加了一個(gè)障礙物，障礙物位置的可能路徑為0。同時(shí)注意初始化的時(shí)候如果初始化的兩邊有一個(gè)障礙物，那么障礙物后面的格子路徑數(shù)都為0。

代碼如下：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m=obstacleGrid.length;int n=obstacleGrid[0].length;int[][] dp=new int[m][n];for(int i=0;i<m && obstacleGrid[i][0]==0;i++) dp[i][0]=1;for(int j=0;j<n && obstacleGrid[0][j]==0;j++) dp[0][j]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=obstacleGrid[i][j]==0?dp[i-1][j]+dp[i][j-1]:0;}}return dp[m-1][n-1];}
}

343.整數(shù)拆分

思路：求一個(gè)數(shù)i拆分后乘積的最大值，考慮從讓j從1開始遍歷計(jì)算j*(i-j)和j*dp[i-j]，也就是說看分成兩部分和分成多個(gè)部分哪個(gè)更大，保留更大的那個(gè)。

動(dòng)規(guī)五部曲

1、確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i]：分拆數(shù)字i，可以得到的最大乘積為dp[i]。

2、確定遞推公式
遞推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

在取最大值的時(shí)候，還需要比較dp[i]是因?yàn)閷?duì)于每一個(gè)j都會(huì)得到一個(gè)dp[i]，最后需要保留最大值。

3、dp的初始化
dp[0] dp[1] ，無法拆分，不進(jìn)行初始化，從dp[2] = 1開始。

4、確定遍歷順序
遞歸公式dp[i] 依靠 dp[i - j]，所以遍歷i一定是從前向后遍歷，先有dp[i - j]再有dp[i]。

5、舉例推導(dǎo)dp數(shù)組

注意:遍歷j的時(shí)候遍歷到i/2即可，因?yàn)榍懊媸遣鸱指蟮牡臄?shù)，當(dāng)j>i/2時(shí)開始拆分小數(shù)，拆分大的數(shù)得到的乘積會(huì)更大。

代碼如下：

class Solution {public int integerBreak(int n) {int[] dp=new int[n+1];dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<=i/2;j++){dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
}

96.不同的二叉搜索樹

思路：dp[3]，就是 元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量

元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有2個(gè)元素的搜索樹數(shù)量 * 左子樹有0個(gè)元素的搜索樹數(shù)量

元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有1個(gè)元素的搜索樹數(shù)量 * 左子樹有1個(gè)元素的搜索樹數(shù)量

元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有0個(gè)元素的搜索樹數(shù)量 * 左子樹有2個(gè)元素的搜索樹數(shù)量

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

動(dòng)規(guī)五部曲

1、確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i] ： 1到i為節(jié)點(diǎn)組成的二叉搜索樹的個(gè)數(shù)為dp[i]。

2、確定遞推公式
在上面的分析中，其實(shí)已經(jīng)看出其遞推關(guān)系， dp[i] += dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量] （j相當(dāng)于是頭結(jié)點(diǎn)的元素，從1遍歷到i為止。）

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量，i-j 為以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量。

3、dp數(shù)組如何初始化
初始化，只需要初始化dp[0]就可以了，從定義上來講，空節(jié)點(diǎn)也是一棵二叉樹，也是一棵二叉搜索樹。初始化dp[0] = 1

4、確定遍歷順序
從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節(jié)點(diǎn)數(shù)為i的狀態(tài)是依靠 i之前節(jié)點(diǎn)數(shù)的狀態(tài)。

5、舉例推導(dǎo)dp數(shù)組

代碼如下：

class Solution {public int numTrees(int n) {int[] dp=new int[n+1];dp[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
}

注：代碼雖然看起來很簡(jiǎn)單，但思路并不容易想到，應(yīng)熟悉掌握思路的形成方式以及動(dòng)規(guī)五部曲的使用。