題目：62.不同路徑

1.二維dp數組dp[i][j]含義：到達（i，j）位置有dp[i][j]種方法。

2.動態轉移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

3.初始化：dp[0][j] = 1, dp[i][0] = 1 （第一行第一列都為1）

4.遍歷順序：從上向下，從左往右

5.打印dp

二維數組怎么定義？

代碼如下：

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for(int i = 0; i < m; i++){dp[i][0] = 1;}for(int j = 0; j < n; j++){dp[0][j] = 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.不同路徑||

思路：

1.dp數組及含義：到達（i，j）位置有dp[i][j]種方法。

2.狀態轉移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]（遇到空位置才進行計算）

3.初始化：dp[0][j] = 1, dp[i][0] = 1 （第一行第一列都為1）。當遇到障礙后停止。

4.遍歷順序：從上向下，從左往右

5.打印dp

代碼如下：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));for(int i = 0; i < obstacleGrid.size() && obstacleGrid[i][0] == 0; i++){dp[i][0] = 1;}for(int j = 0; j < obstacleGrid[0].size() && obstacleGrid[0][j] == 0; j++){dp[0][j] = 1;}for(int i = 1; i < obstacleGrid.size(); i++){for(int j = 1; j <obstacleGrid[0].size(); j++){if(obstacleGrid[i][j] == 0){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];}
};

題目：343.整數拆分

關鍵在于理解遞推公式。（考慮好有幾個需要比較的情況）

什么時候乘積最大？拆成盡可能相等的數

思路：

1.dp含義：數i經過拆分后，得到最大的乘積dp[i]

2.狀態轉移方程（dp[i] 是依靠 dp[i - j]的狀態）：

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

? ? ? ? 1)有兩種拆分方式：一是i * (i - j)直接相乘（把 i 拆成兩個數）；

????????????????????????????????????二是 j * dp[i - j]（把 i 拆成三個數及以上）?????????

? ? ? ? 2)在遞推公式推導的過程中，每次計算dp[i]，取最大的而已

? ? ? ? ? ? ? ? 因為在第二層循環中會不斷得到新的dp[i]，用本輪for循環得到的dp[i]與之前得到的最大的dp[i]作比較，取更大的。

3.初始化：

拆分0和拆分1的最大乘積是多少？

這是無解的。

這里我只初始化dp[2] = 1，從dp[i]的定義來說，拆分數字2，得到的最大乘積是1，這個沒有任何異議！確定遍歷順序，先來看看遞歸公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

4.確定遍歷順序：從前到后

確定遍歷順序，先來看看遞歸公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的狀態，所以遍歷i一定是從前向后遍歷，先有dp[i - j]再有dp[i]。

5.打印dp數組：

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

題目：96.不同的二叉搜索樹

思路：

1.dp數組含義：含有 i 個節點的二叉搜索樹共有dp[i]種

2.狀態轉移方程：

dp[3]，就是 元素1為頭結點搜索樹的數量 + 元素2為頭結點搜索樹的數量 + 元素3為頭結點搜索樹的數量

元素1為頭結點搜索樹的數量 = 右子樹有2個元素的搜索樹數量 * 左子樹有0個元素的搜索樹數量

元素2為頭結點搜索樹的數量 = 右子樹有1個元素的搜索樹數量 * 左子樹有1個元素的搜索樹數量

元素3為頭結點搜索樹的數量 = 右子樹有0個元素的搜索樹數量 * 左子樹有2個元素的搜索樹數量

有2個元素的搜索樹數量就是dp[2]。

有1個元素的搜索樹數量就是dp[1]。

有0個元素的搜索樹數量就是dp[0]。

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

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結點左子樹節點數量，i-j 為以j為頭結點右子樹節點數量

3.初始化：

初始化，只需要初始化dp[0]就可以了，推導的基礎，都是dp[0]。

那么dp[0]應該是多少呢？

從定義上來講，空節點也是一棵二叉樹，也是一棵二叉搜索樹，這是可以說得通的。

從遞歸公式上來講，dp[以j為頭結點左子樹節點數量] * dp[以j為頭結點右子樹節點數量] 中以j為頭結點左子樹節點數量為0，也需要dp[以j為頭結點左子樹節點數量] = 1， 否則乘法的結果就都變成0了。

4.遍歷順序：左往右

5.打印dp

容易犯得典型錯誤：

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;      //易錯：空二叉樹也是二叉搜索樹dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i++){      //統計以1，2,...,n為結點有多少種不同的二叉樹for(int j = 1; j <= i; j++){     //統計以1，2,...,i為頭結點，同時共n個節點，有多少種不同的二叉樹dp[i] += dp[j - 1] * dp[i - j]; }}return dp[n];}
};

在初始化時賦值dp[2]等于0，如果題目中n = 1,則會越界。

這一點很容易犯錯

其實經常會有一個困惑，到底初始化時要初始前多少個呢？（手動模擬一下）

正確代碼如下：

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[0] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= i / 2; j++){dp[i] = max(max(j * (i - j), j * dp[i - j]), dp[i]);}}return dp[n];}
};

其實只用定義dp[0] = 0，dp[1]往后都是可以動態規劃循環推出來的。