目錄

509.斐波那契數(shù)?

70.爬樓梯

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

62.不同路徑

63.不同路徑||

343.整數(shù)拆分

96.不同的二叉樹

?

509.斐波那契數(shù)?

509. 斐波那契數(shù)

簡單

斐波那契數(shù)?（通常用?F(n)?表示）形成的序列稱為?斐波那契數(shù)列?。該數(shù)列由?0?和?1?開始，后面的每一項數(shù)字都是前面兩項數(shù)字的和。也就是：

F(0) = 0，F(xiàn)(1)?= 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定?n?，請計算?F(n)?。

示例 1：

輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

確定dp數(shù)組以及下標(biāo)的含義

dp[i]的定義為：第i個數(shù)的斐波那契數(shù)值是dp[i]

確定遞推公式

狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i - 1] + dp[i - 2];

dp數(shù)組如何初始化

dp[0] = 0;
dp[1] = 1;

確定遍歷順序

從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的

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

按照這個遞推公式dp[i] = dp[i - 1] + dp[i - 2]，我們來推導(dǎo)一下，當(dāng)N為10的時候，dp數(shù)組應(yīng)該是如下的數(shù)列：

0 1 1 2 3 5 8 13 21 34 55

如果代碼寫出來，發(fā)現(xiàn)結(jié)果不對，就把dp數(shù)組打印出來看看和我們推導(dǎo)的數(shù)列是不是一致的。

// 定義一個名為Solution的類  
class Solution {  
    // 定義一個公共方法fib，用于計算斐波那契數(shù)列的第n個數(shù)  
    public int fib(int n) {  
        // 如果n小于2，直接返回n。這是斐波那契數(shù)列的基礎(chǔ)情況，即f(0) = 0, f(1) = 1  
        if(n < 2){  
            return n;  
        }  
          
        // 定義一個數(shù)組dp，長度為n+1，用于存儲斐波那契數(shù)列的值  
        int dp[] = new int[n + 1];  
          
        // 初始化斐波那契數(shù)列的前兩個數(shù)  
        dp[0] = 0; // f(0) = 0  
        dp[1] = 1; // f(1) = 1  
          
        // 從第2個數(shù)開始，通過循環(huán)計算斐波那契數(shù)列的剩余值  
        for(int i = 2; i <= n; i++){  
            // 斐波那契數(shù)列的定義：f(i) = f(i-1) + f(i-2)，這里計算并存儲第i個斐波那契數(shù)  
            dp[i] = dp[i - 1] + dp[i - 2];  
        }   
          
        // 返回第n個斐波那契數(shù)  
        return dp[n];  
    }  
}

70.爬樓梯

70. 爬樓梯

簡單

提示

假設(shè)你正在爬樓梯。需要?n?階你才能到達(dá)樓頂。

每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

• 1 <= n <= 45

確定dp數(shù)組以及下標(biāo)的含義

dp[i]： 爬到第i層樓梯，有dp[i]種方法

確定遞推公式

首先是dp[i - 1]，上i-1層樓梯，有dp[i - 1]種方法，那么再一步跳一個臺階不就是dp[i]了么。

還有就是dp[i - 2]，上i-2層樓梯，有dp[i - 2]種方法，那么再一步跳兩個臺階不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]與dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推導(dǎo)dp[i]的時候，一定要時刻想著dp[i]的定義，否則容易跑偏。

這體現(xiàn)出確定dp數(shù)組以及下標(biāo)的含義的重要性！

dp數(shù)組如何初始化

再回顧一下dp[i]的定義：爬到第i層樓梯，有dp[i]種方法。

我dp[1] = 1，dp[2] = 2，這個初始化大家應(yīng)該都沒有爭議的。

所以我的原則是：不考慮dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后從i = 3開始遞推，這樣才符合dp[i]的定義。

確定遍歷順序

從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的

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

舉例當(dāng)n為5的時候，dp table（dp數(shù)組）應(yīng)該是這樣的

如果代碼出問題了，就把dp table 打印出來，看看究竟是不是和自己推導(dǎo)的一樣。

// 定義一個名為Solution的類  
class Solution {  
    // 定義一個公共方法climbStairs，用于計算爬樓梯的不同方式的數(shù)量  
    public int climbStairs(int n) {  
        // 如果樓梯的階數(shù)小于3，則直接返回階數(shù)本身，因?yàn)?階和2階的爬樓梯方式數(shù)就是階數(shù)本身  
        if(n < 3){  
            return n;  
        }  
          
        // 定義一個數(shù)組dp，長度為n+1，用于存儲到達(dá)每一階樓梯的不同方式的數(shù)量  
        int dp[] = new int[n + 1];  
          
        // 初始化到達(dá)第1階樓梯的方式有1種，即直接跨一步  
        dp[1] = 1;  
          
        // 初始化到達(dá)第2階樓梯的方式有2種，即跨一步或跨兩步  
        dp[2] = 2;  
          
        // 從第3階樓梯開始，通過循環(huán)計算到達(dá)每一階樓梯的不同方式的數(shù)量  
        for(int i = 3; i <= n; i++){  
            // 到達(dá)第i階樓梯的方式數(shù)是到達(dá)第i-1階樓梯的方式數(shù)加上到達(dá)第i-2階樓梯的方式數(shù)  
            // 因?yàn)榭梢詮牡趇-1階跨一步上來，也可以從第i-2階跨兩步上來  
            dp[i] = dp[i - 1] + dp[i - 2];  
        }  
          
        // 返回到達(dá)第n階樓梯的不同方式的數(shù)量  
        return dp[n];  
    }  
}

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

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

簡單

提示

給你一個整數(shù)數(shù)組?cost?，其中?cost[i]?是從樓梯第?i?個臺階向上爬需要支付的費(fèi)用。一旦你支付此費(fèi)用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標(biāo)為?0?或下標(biāo)為?1?的臺階開始爬樓梯。

請你計算并返回達(dá)到樓梯頂部的最低花費(fèi)。

示例 1：

輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標(biāo)為 1 的臺階開始。
- 支付 15 ，向上爬兩個臺階，到達(dá)樓梯頂部。
總花費(fèi)為 15 。

示例 2：

輸入：cost = [1,100,1,1,1,100,1,1,100,1]
輸出：6
解釋：你將從下標(biāo)為 0 的臺階開始。
- 支付 1 ，向上爬兩個臺階，到達(dá)下標(biāo)為 2 的臺階。
- 支付 1 ，向上爬兩個臺階，到達(dá)下標(biāo)為 4 的臺階。
- 支付 1 ，向上爬兩個臺階，到達(dá)下標(biāo)為 6 的臺階。
- 支付 1 ，向上爬一個臺階，到達(dá)下標(biāo)為 7 的臺階。
- 支付 1 ，向上爬兩個臺階，到達(dá)下標(biāo)為 9 的臺階。
- 支付 1 ，向上爬一個臺階，到達(dá)樓梯頂部。
總花費(fèi)為 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

題目中說 “你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺階開始爬樓梯” 也就是相當(dāng)于 跳到 下標(biāo) 0 或者 下標(biāo) 1 是不花費(fèi)體力的， 從 下標(biāo) 0 下標(biāo)1 開始跳就要花費(fèi)體力了。

確定dp數(shù)組以及下標(biāo)的含義

dp[i]的定義：到達(dá)第i臺階所花費(fèi)的最少體力為dp[i]。

確定遞推公式

可以有兩個途徑得到dp[i]，一個是dp[i-1] 一個是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花費(fèi) dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花費(fèi) dp[i - 2] + cost[i - 2]。

那么究竟是選從dp[i - 1]跳還是從dp[i - 2]跳呢？

一定是選最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

dp數(shù)組如何初始化

題目描述中明確說了 “你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺階開始爬樓梯?！?也就是說 到達(dá) 第 0 個臺階是不花費(fèi)的，但從 第0 個臺階 往上跳的話，需要花費(fèi) cost[0]。

所以初始化 dp[0] = 0，dp[1] = 0;

確定遍歷順序

本題的遍歷順序其實(shí)比較簡單，簡單到很多同學(xué)都忽略了思考這一步直接就把代碼寫出來了。

因?yàn)槭悄M臺階，而且dp[i]由dp[i-1]dp[i-2]推出，所以是從前到后遍歷cost數(shù)組就可以了。

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

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，來模擬一下dp數(shù)組的狀態(tài)變化，如下：

如果大家代碼寫出來有問題，就把dp數(shù)組打印出來，看看和如上推導(dǎo)的是不是一樣的。

class Solution {  
    // 公共方法，計算爬樓梯的最小花費(fèi)  
    public int minCostClimbingStairs(int[] cost) {  
        // 如果樓梯的階數(shù)小于2，則不需要花費(fèi)，直接返回0  
        if(cost.length < 2){  
            return 0;  
        }  
          
        // 定義一個數(shù)組dp，長度為cost.length + 1，用于存儲到達(dá)每一階樓梯的最小花費(fèi)  
        int dp[] = new int[cost.length + 1];  
          
        // 初始化到達(dá)第0階樓梯的花費(fèi)為0，這通常是為了確保代碼邏輯的完整性，實(shí)際中沒有第0階樓梯  
        dp[0] = 0;  
          
        // 初始化到達(dá)第1階樓梯的花費(fèi)為0，因?yàn)榈竭_(dá)第1階樓梯不需要跨越任何樓梯，所以花費(fèi)為0  
        dp[1] = 0;  
          
        // 從第2階樓梯開始，通過循環(huán)計算到達(dá)每一階樓梯的最小花費(fèi)  
        for(int i = 2; i <= cost.length; i++){  
            // 到達(dá)第i階樓梯的最小花費(fèi)是選擇從第i-1階跨一步上來或從第i-2階跨兩步上來的較小花費(fèi)  
            // 加上對應(yīng)階數(shù)的花費(fèi)cost[i-1]或cost[i-2]  
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);  
        }  
          
        // 返回到達(dá)最高階樓梯（第cost.length階）的最小花費(fèi)  
        return dp[cost.length];  
    }  
}

62.不同路徑

62. 不同路徑

中等

一個機(jī)器人位于一個?m x n?網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。

機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。

問總共有多少條不同的路徑？

示例 1：

輸入：m = 3, n = 7
輸出：28

示例 2：

輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

輸入：m = 7, n = 3
輸出：28

示例 4：

輸入：m = 3, n = 3
輸出：6

提示：

• 1 <= m, n <= 100
• 題目數(shù)據(jù)保證答案小于等于?2 * 109

確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

確定遞推公式

想要求dp[i][j]，只能有兩個方向來推導(dǎo)出來，即dp[i - 1][j] 和 dp[i][j - 1]。

此時在回顧一下 dp[i - 1][j] 表示啥，是從(0, 0)的位置到(i - 1, j)有幾條路徑，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因?yàn)閐p[i][j]只有這兩個方向過來。

dp數(shù)組的初始化

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

所以初始化代碼為：

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

確定遍歷順序

這里要看一下遞推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是從其上方和左方推導(dǎo)而來，那么從左到右一層一層遍歷就可以了。

這樣就可以保證推導(dǎo)dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值的。

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

如圖所示：

class Solution {  
    // 這個函數(shù)計算從左上角到右下角的唯一路徑數(shù)，其中網(wǎng)格的維度是m行n列  
    public static int uniquePaths(int m, int n) {  
          
        // 使用一個二維數(shù)組dp來存儲到達(dá)每個格子的唯一路徑數(shù)  
        int[][] dp = new int[m][n];  
  
        // 初始化第一列的所有格子，因?yàn)閺淖笊辖堑降谝涣械娜魏我粋€格子都只有一條路徑  
        for (int i = 0; i < m; i++) {  
            dp[i][0] = 1;  
        }  
  
        // 初始化第一行的所有格子，因?yàn)閺淖笊辖堑降谝恍械娜魏我粋€格子也只有一條路徑  
        for (int i = 0; i < n; i++) {  
            dp[0][i] = 1;  
        }  
  
        // 從第二行第二列開始，計算到達(dá)每個格子的唯一路徑數(shù)  
        // 路徑數(shù)等于其上方格子的路徑數(shù)加上其左方格子的路徑數(shù)  
        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];  
            }  
        }  
  
        // 返回右下角格子的路徑數(shù)，即從左上角到右下角的唯一路徑數(shù)  
        return dp[m-1][n-1];  
    }  
}

63.不同路徑||

63. 不同路徑 II

中等

提示

一個機(jī)器人位于一個?m x n?網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。

機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用?1?和?0?來表示。

示例 1：

輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網(wǎng)格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1

提示：

• m ==?obstacleGrid.length
• n ==?obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j]?為?0?或?1

確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

確定遞推公式

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

但這里需要注意一點(diǎn)，因?yàn)橛辛苏系K，(i, j)如果就是障礙的話應(yīng)該就保持初始狀態(tài)（初始狀態(tài)為0）。

dp數(shù)組如何初始化

因?yàn)閺?0, 0)的位置到(i, 0)的路徑只有一條，所以dp[i][0]一定為1，dp[0][j]也同理。

但如果(i, 0) 這條邊有了障礙之后，障礙之后（包括障礙）都是走不到的位置了，所以障礙之后的dp[i][0]應(yīng)該還是初始值0。

如圖：

下標(biāo)(0, j)的初始化情況同理。

注意代碼里for循環(huán)的終止條件，一旦遇到obstacleGrid[i][0] == 1的情況就停止dp[i][0]的賦值1的操作，dp[0][j]同理

確定遍歷順序

從遞歸公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，一定是從左到右一層一層遍歷，這樣保證推導(dǎo)dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值。

代碼如下：

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

拿示例1來舉例如題：

對應(yīng)的dp table 如圖：

class Solution {  
    // 這個函數(shù)計算從左上角到右下角的唯一路徑數(shù)，其中網(wǎng)格中可能包含障礙物  
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {  
        // 創(chuàng)建一個二維數(shù)組dp來存儲到達(dá)每個格子的唯一路徑數(shù)  
        int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];  
  
        // 初始化第一行  
        for (int i = 0; i < obstacleGrid[0].length; i++) {  
            // 如果當(dāng)前格子是障礙物，則路徑數(shù)為0  
            if (obstacleGrid[0][i] == 1) {  
                dp[0][i] = 0;  
            } else {  
                // 如果不是第一列，則路徑數(shù)等于前一個格子的路徑數(shù)  
                if (i > 0) {  
                    dp[0][i] = dp[0][i - 1];  
                } else {  
                    // 如果是第一列且沒有障礙物，則路徑數(shù)為1  
                    dp[0][i] = 1;  
                }  
            }  
        }  
  
        // 初始化第一列  
        for (int i = 0; i < obstacleGrid.length; i++) {  
            // 如果當(dāng)前格子是障礙物，則路徑數(shù)為0  
            if (obstacleGrid[i][0] == 1) {  
                dp[i][0] = 0;  
            } else {  
                // 如果不是第一行，則路徑數(shù)等于上一個格子的路徑數(shù)  
                if (i > 0) {  
                    dp[i][0] = dp[i - 1][0];  
                } else {  
                    // 如果是第一行且沒有障礙物，則路徑數(shù)為1  
                    dp[i][0] = 1;  
                }  
            }  
        }  
  
        // 從第二行第二列開始計算每個格子的路徑數(shù)  
        for (int i = 1; i < obstacleGrid.length; i++) {  
            for (int j = 1; j < obstacleGrid[0].length; j++) {  
                // 如果當(dāng)前格子是障礙物，則路徑數(shù)為0  
                if (obstacleGrid[i][j] == 1) {  
                    dp[i][j] = 0;  
                } else {  
                    // 否則，路徑數(shù)等于上方格子的路徑數(shù)加上左方格子的路徑數(shù)  
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];  
                }  
            }  
        }  
  
        // 返回右下角格子的路徑數(shù)，即從左上角到右下角的唯一路徑數(shù)  
        return dp[dp.length - 1][dp[0].length - 1];  
    }  
}

?因?yàn)槌跏蓟膁p數(shù)組中所有的值均為0，所以在遇到障礙的情況下不需要將dp數(shù)組賦值為0，直接跳過就可以

class Solution {  
    // 這個函數(shù)計算從左上角到右下角的唯一路徑數(shù)，其中網(wǎng)格中可能包含障礙物  
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {  
        // 創(chuàng)建一個二維數(shù)組dp來存儲到達(dá)每個格子的唯一路徑數(shù)  
        int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];  
  
        // 初始化第一行  
        for (int i = 0; i < obstacleGrid[0].length && obstacleGrid[0][i] == 0; i++) {  
            // 如果當(dāng)前格子是障礙物，則該格子dp不變（為0），且跳出循環(huán)，同一行之后的格子dp也不變    
            //格子左邊無障礙物，dp為1
                dp[0][i] = 1;  
        }  
  
        // 初始化第一列  
        for (int i = 0; i < obstacleGrid.length && obstacleGrid[i][0] == 0; i++) {  
            // 如果當(dāng)前格子是障礙物，則該格子dp不變（為0），且跳出循環(huán)，同一列之后的格子dp也不變          
            //格子上邊無障礙物，dp為1
            dp[i][0] = 1;   
        }  
  
        // 從第二行第二列開始計算每個格子的路徑數(shù)  
        for (int i = 1; i < obstacleGrid.length; i++) {  
            for (int j = 1; j < obstacleGrid[0].length; j++) {  
                // 如果當(dāng)前格子不是障礙物，則路徑數(shù)為0 ，是障礙物dp不變（為0） 
                if (obstacleGrid[i][j] != 1) {  
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
                } 
            }  
        }  
  
        // 返回右下角格子的路徑數(shù)，即從左上角到右下角的唯一路徑數(shù)  
        return dp[dp.length - 1][dp[0].length - 1];  
    }  
}

343.整數(shù)拆分

343. 整數(shù)拆分

中等

提示

給定一個正整數(shù)?n?，將其拆分為?k?個?正整數(shù)?的和（?k >= 2?），并使這些整數(shù)的乘積最大化。

返回?你可以獲得的最大乘積?。

示例 1:

輸入: n = 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。

示例?2:

輸入: n = 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 ×?3 ×?4 = 36。

提示:

• 2 <= n <= 58

確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i]：分拆數(shù)字i，可以得到的最大乘積為dp[i]。

dp[i]的定義將貫徹整個解題過程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

確定遞推公式

可以想 dp[i]最大乘積是怎么得到的呢？

其實(shí)可以從1遍歷j，然后有兩種渠道得到dp[i].

一個是j * (i - j) 直接相乘。

一個是j * dp[i - j]，相當(dāng)于是拆分(i - j)，對這個拆分不理解的話，可以回想dp數(shù)組的定義。

那有同學(xué)問了，j怎么就不拆分呢？

j是從1開始遍歷，拆分j的情況，在遍歷j的過程中其實(shí)都計算過了。那么從1遍歷j，比較(i - j) * j和dp[i - j] * j 取最大的。遞推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

也可以這么理解，j * (i - j) 是單純的把整數(shù)拆分為兩個數(shù)相乘，而j * dp[i - j]是拆分成兩個以及兩個以上的個數(shù)相乘。

如果定義dp[i - j] * dp[j] 也是默認(rèn)將一個數(shù)強(qiáng)制拆成4份以及4份以上了。

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

那么在取最大值的時候，為什么還要比較dp[i]呢？

因?yàn)樵谶f推公式推導(dǎo)的過程中，每次計算dp[i]，取最大的而已。

dp的初始化

嚴(yán)格從dp[i]的定義來說，dp[0] dp[1] 就不應(yīng)該初始化，也就是沒有意義的數(shù)值。

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

這是無解的。

這里我只初始化dp[2] = 1，從dp[i]的定義來說，拆分?jǐn)?shù)字2，得到的最大乘積是1，這個沒有任何異議！

確定遍歷順序

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

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

所以遍歷順序?yàn)椋?/p>

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

注意 枚舉j的時候，是從1開始的。從0開始的話，那么讓拆分一個數(shù)拆個0，求最大乘積就沒有意義了。

j的結(jié)束條件是 j < i - 1 ，其實(shí) j < i 也是可以的，不過可以節(jié)省一步，例如讓j = i - 1，的話，其實(shí)在 j = 1的時候，這一步就已經(jīng)拆出來了，重復(fù)計算，所以 j < i - 1

至于 i是從3開始，這樣dp[i - j]就是dp[2]正好可以通過我們初始化的數(shù)值求出來。

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

舉例當(dāng)n為10的時候，dp數(shù)組里的數(shù)值，如下：

class Solution {  
    public int integerBreak(int n) {  
        // 創(chuàng)建一個動態(tài)規(guī)劃數(shù)組，dp[i] 表示將正整數(shù) i 拆分后得到的最大乘積  
        int[] dp = new int[n + 1];  
          
        // 初始化基礎(chǔ)情況，將正整數(shù)2拆分只有一個拆分方式即2本身，因此乘積為1  
        dp[2] = 1;  
          
        // 從3開始遍歷到n，計算每個數(shù)的最大乘積  
        for (int i = 3; i <= n; i++) {  
            // 對于每個數(shù)i，遍歷所有可能的拆分方式j(luò)  
            for (int j = 1; j <= i; j++) {  
                // 計算當(dāng)前拆分方式的乘積，有兩種可能：  
                // 1. 直接將j和(i-j)相乘  
                // 2. 將j與剩下的數(shù)(i-j)拆分后的最大乘積相乘  
                // 取兩種可能中的較大值更新dp[i]  
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));  
            }  
        }  
          
        // 返回正整數(shù)n拆分后的最大乘積  
        return dp[n];  
    }  
}

96.不同的二叉樹

96. 不同的二叉搜索樹

相關(guān)標(biāo)簽

相關(guān)企業(yè)

給你一個整數(shù)?n?，求恰由?n?個節(jié)點(diǎn)組成且節(jié)點(diǎn)值從?1?到?n?互不相同的?二叉搜索樹?有多少種？返回滿足題意的二叉搜索樹的種數(shù)。

示例 1：

輸入：n = 3
輸出：5

示例 2：

輸入：n = 1
輸出：1

提示：

• 1 <= n <= 19

了解了二叉搜索樹之后，我們應(yīng)該先舉幾個例子，畫畫圖，看看有沒有什么規(guī)律，如圖：

n為1的時候有一棵樹，n為2有兩棵樹，這個是很直觀的。

來看看n為3的時候，有哪幾種情況。

當(dāng)1為頭結(jié)點(diǎn)的時候，其右子樹有兩個節(jié)點(diǎn)，看這兩個節(jié)點(diǎn)的布局，是不是和 n 為2的時候兩棵樹的布局是一樣的??！

（可能有同學(xué)問了，這布局不一樣啊，節(jié)點(diǎn)數(shù)值都不一樣。別忘了我們就是求不同樹的數(shù)量，并不用把搜索樹都列出來，所以不用關(guān)心其具體數(shù)值的差異）

當(dāng)3為頭結(jié)點(diǎn)的時候，其左子樹有兩個節(jié)點(diǎn)，看這兩個節(jié)點(diǎn)的布局，是不是和n為2的時候兩棵樹的布局也是一樣的啊！

當(dāng)2為頭結(jié)點(diǎn)的時候，其左右子樹都只有一個節(jié)點(diǎn)，布局是不是和n為1的時候只有一棵樹的布局也是一樣的??！

發(fā)現(xiàn)到這里，其實(shí)我們就找到了重疊子問題了，其實(shí)也就是發(fā)現(xiàn)可以通過dp[1] 和 dp[2] 來推導(dǎo)出來dp[3]的某種方式。

思考到這里，這道題目就有眉目了。

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

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

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

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

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

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

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

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

如圖所示：

此時我們已經(jīng)找到遞推關(guān)系了，那么可以用動規(guī)五部曲再系統(tǒng)分析一遍。

確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i] ： 1到i為節(jié)點(diǎn)組成的二叉搜索樹的個數(shù)為dp[i]。

也可以理解是i個不同元素節(jié)點(diǎn)組成的二叉搜索樹的個數(shù)為dp[i] ，都是一樣的。

確定遞推公式

在上面的分析中，其實(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ù)量

dp數(shù)組如何初始化

初始化，只需要初始化dp[0]就可以了，推導(dǎo)的基礎(chǔ)，都是dp[0]。

那么dp[0]應(yīng)該是多少呢？

從定義上來講，空節(jié)點(diǎn)也是一棵二叉樹，也是一棵二叉搜索樹，這是可以說得通的。

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

所以初始化dp[0] = 1

確定遍歷順序

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

那么遍歷i里面每一個數(shù)作為頭結(jié)點(diǎn)的狀態(tài)，用j來遍歷。

代碼如下：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
    }
}

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

n為5時候的dp數(shù)組狀態(tài)如圖：

當(dāng)然如果自己畫圖舉例的話，基本舉例到n為3就可以了，n為4的時候，畫圖已經(jīng)比較麻煩了。

我這里列到了n為5的情況，是為了方便大家 debug代碼的時候，把dp數(shù)組打出來，看看哪里有問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-841170.html

class Solution {  
    public int numTrees(int n) {  
        // 創(chuàng)建一個動態(tài)規(guī)劃數(shù)組dp，dp[i]表示由1到i這些整數(shù)能構(gòu)成的不同二叉搜索樹的個數(shù)  
        int[] dp = new int[n + 1];  
        // 初始化dp數(shù)組，空樹和只有一個節(jié)點(diǎn)的樹都只有1種情況  
        dp[0] = 1;  
        dp[1] = 1;  
          
        // 從2開始遍歷到n，計算每個數(shù)作為根節(jié)點(diǎn)時的不同二叉搜索樹的個數(shù)  
        for(int i = 2; i <= n; i++){  
            // 對于每個i，枚舉1到i之間的每個數(shù)j作為根節(jié)點(diǎn)  
            for(int j = 1; j <= i; j++){  
                // 當(dāng)j作為根節(jié)點(diǎn)時，左子樹由1到j(luò)-1構(gòu)成，右子樹由j+1到i構(gòu)成  
                // 左子樹和右子樹分別可以構(gòu)成dp[j-1]和dp[i-j]個不同的二叉搜索樹  
                // 因此，以j為根節(jié)點(diǎn)的不同二叉搜索樹的個數(shù)為左子樹個數(shù)乘以右子樹個數(shù)  
                // 累加所有以不同數(shù)為根節(jié)點(diǎn)的情況，得到dp[i]  
                dp[i] += dp[j - 1] * dp[i - j];  
            }  
        }  
        // 返回由1到n這些整數(shù)能構(gòu)成的不同二叉搜索樹的個數(shù)  
        return dp[n];  
    }  
}

到了這里，關(guān)于代碼隨想錄 動態(tài)規(guī)劃-基礎(chǔ)題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！