代码随想录 动态规划-基础题目

目录

509.斐波那契数 

70.爬楼梯

746.使用最小花费爬楼梯

62.不同路径

63.不同路径||

343.整数拆分

96.不同的二叉树

509.斐波那契数 

509. 斐波那契数

简单

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(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数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

确定递推公式

状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

dp数组如何初始化

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

确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

// 定义一个名为Solution的类  
class Solution {  
    // 定义一个公共方法fib，用于计算斐波那契数列的第n个数  
    public int fib(int n) {  
        // 如果n小于2，直接返回n。这是斐波那契数列的基础情况，即f(0) = 0, f(1) = 1  
        if(n < 2){  
            return n;  
        }  
          
        // 定义一个数组dp，长度为n+1，用于存储斐波那契数列的值  
        int dp[] = new int[n + 1];  
          
        // 初始化斐波那契数列的前两个数  
        dp[0] = 0; // f(0) = 0  
        dp[1] = 1; // f(1) = 1  
          
        // 从第2个数开始，通过循环计算斐波那契数列的剩余值  
        for(int i = 2; i <= n; i++){  
            // 斐波那契数列的定义：f(i) = f(i-1) + f(i-2)，这里计算并存储第i个斐波那契数  
            dp[i] = dp[i - 1] + dp[i - 2];  
        }   
          
        // 返回第n个斐波那契数  
        return dp[n];  
    }  
}

70.爬楼梯

70. 爬楼梯

简单

提示

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 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数组以及下标的含义

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] 。

在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性！

dp数组如何初始化

再回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]种方法。

我dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。

所以我的原则是：不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

举例推导dp数组

举例当n为5的时候，dp table（dp数组）应该是这样的

如果代码出问题了，就把dp table 打印出来，看看究竟是不是和自己推导的一样。

// 定义一个名为Solution的类  
class Solution {  
    // 定义一个公共方法climbStairs，用于计算爬楼梯的不同方式的数量  
    public int climbStairs(int n) {  
        // 如果楼梯的阶数小于3，则直接返回阶数本身，因为1阶和2阶的爬楼梯方式数就是阶数本身  
        if(n < 3){  
            return n;  
        }  
          
        // 定义一个数组dp，长度为n+1，用于存储到达每一阶楼梯的不同方式的数量  
        int dp[] = new int[n + 1];  
          
        // 初始化到达第1阶楼梯的方式有1种，即直接跨一步  
        dp[1] = 1;  
          
        // 初始化到达第2阶楼梯的方式有2种，即跨一步或跨两步  
        dp[2] = 2;  
          
        // 从第3阶楼梯开始，通过循环计算到达每一阶楼梯的不同方式的数量  
        for(int i = 3; i <= n; i++){  
            // 到达第i阶楼梯的方式数是到达第i-1阶楼梯的方式数加上到达第i-2阶楼梯的方式数  
            // 因为可以从第i-1阶跨一步上来，也可以从第i-2阶跨两步上来  
            dp[i] = dp[i - 1] + dp[i - 2];  
        }  
          
        // 返回到达第n阶楼梯的不同方式的数量  
        return dp[n];  
    }  
}

746.使用最小花费爬楼梯

746. 使用最小花费爬楼梯

简单

提示

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

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

题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了。

确定dp数组以及下标的含义

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[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数组如何初始化

题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。

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

确定遍历顺序

本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。

举例推导dp数组

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。

class Solution {  
    // 公共方法，计算爬楼梯的最小花费  
    public int minCostClimbingStairs(int[] cost) {  
        // 如果楼梯的阶数小于2，则不需要花费，直接返回0  
        if(cost.length < 2){  
            return 0;  
        }  
          
        // 定义一个数组dp，长度为cost.length + 1，用于存储到达每一阶楼梯的最小花费  
        int dp[] = new int[cost.length + 1];  
          
        // 初始化到达第0阶楼梯的花费为0，这通常是为了确保代码逻辑的完整性，实际中没有第0阶楼梯  
        dp[0] = 0;  
          
        // 初始化到达第1阶楼梯的花费为0，因为到达第1阶楼梯不需要跨越任何楼梯，所以花费为0  
        dp[1] = 0;  
          
        // 从第2阶楼梯开始，通过循环计算到达每一阶楼梯的最小花费  
        for(int i = 2; i <= cost.length; i++){  
            // 到达第i阶楼梯的最小花费是选择从第i-1阶跨一步上来或从第i-2阶跨两步上来的较小花费  
            // 加上对应阶数的花费cost[i-1]或cost[i-2]  
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);  
        }  
          
        // 返回到达最高阶楼梯（第cost.length阶）的最小花费  
        return dp[cost.length];  
    }  
}

62.不同路径

62. 不同路径

中等

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

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

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

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

示例 4：

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

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

确定dp数组（dp table）以及下标的含义

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

确定递推公式

想要求dp[i][j]，只能有两个方向来推导出来，即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]，因为dp[i][j]只有这两个方向过来。

dp数组的初始化

如何初始化呢，首先dp[i][0]一定都是1，因为从(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]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

举例推导dp数组

如图所示：

class Solution {  
    // 这个函数计算从左上角到右下角的唯一路径数，其中网格的维度是m行n列  
    public static int uniquePaths(int m, int n) {  
          
        // 使用一个二维数组dp来存储到达每个格子的唯一路径数  
        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.不同路径||

63. 不同路径 II

中等

提示

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 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数组（dp table）以及下标的含义

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

确定递推公式

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

但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

dp数组如何初始化

因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。

但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。

如图：

下标(0, j)的初始化情况同理。

注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理

确定遍历顺序

从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，一定是从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。

代码如下：

举例推导dp数组

拿示例1来举例如题：

对应的dp table 如图：

class Solution {  
    // 这个函数计算从左上角到右下角的唯一路径数，其中网格中可能包含障碍物  
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {  
        // 创建一个二维数组dp来存储到达每个格子的唯一路径数  
        int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];  
  
        // 初始化第一行  
        for (int i = 0; i < obstacleGrid[0].length; i++) {  
            // 如果当前格子是障碍物，则路径数为0  
            if (obstacleGrid[0][i] == 1) {  
                dp[0][i] = 0;  
            } else {  
                // 如果不是第一列，则路径数等于前一个格子的路径数  
                if (i > 0) {  
                    dp[0][i] = dp[0][i - 1];  
                } else {  
                    // 如果是第一列且没有障碍物，则路径数为1  
                    dp[0][i] = 1;  
                }  
            }  
        }  
  
        // 初始化第一列  
        for (int i = 0; i < obstacleGrid.length; i++) {  
            // 如果当前格子是障碍物，则路径数为0  
            if (obstacleGrid[i][0] == 1) {  
                dp[i][0] = 0;  
            } else {  
                // 如果不是第一行，则路径数等于上一个格子的路径数  
                if (i > 0) {  
                    dp[i][0] = dp[i - 1][0];  
                } else {  
                    // 如果是第一行且没有障碍物，则路径数为1  
                    dp[i][0] = 1;  
                }  
            }  
        }  
  
        // 从第二行第二列开始计算每个格子的路径数  
        for (int i = 1; i < obstacleGrid.length; i++) {  
            for (int j = 1; j < obstacleGrid[0].length; j++) {  
                // 如果当前格子是障碍物，则路径数为0  
                if (obstacleGrid[i][j] == 1) {  
                    dp[i][j] = 0;  
                } else {  
                    // 否则，路径数等于上方格子的路径数加上左方格子的路径数  
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];  
                }  
            }  
        }  
  
        // 返回右下角格子的路径数，即从左上角到右下角的唯一路径数  
        return dp[dp.length - 1][dp[0].length - 1];  
    }  
}

 因为初始化的dp数组中所有的值均为0，所以在遇到障碍的情况下不需要将dp数组赋值为0，直接跳过就可以

class Solution {  
    // 这个函数计算从左上角到右下角的唯一路径数，其中网格中可能包含障碍物  
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {  
        // 创建一个二维数组dp来存储到达每个格子的唯一路径数  
        int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];  
  
        // 初始化第一行  
        for (int i = 0; i < obstacleGrid[0].length && obstacleGrid[0][i] == 0; i++) {  
            // 如果当前格子是障碍物，则该格子dp不变（为0），且跳出循环，同一行之后的格子dp也不变    
            //格子左边无障碍物，dp为1
                dp[0][i] = 1;  
        }  
  
        // 初始化第一列  
        for (int i = 0; i < obstacleGrid.length && obstacleGrid[i][0] == 0; i++) {  
            // 如果当前格子是障碍物，则该格子dp不变（为0），且跳出循环，同一列之后的格子dp也不变          
            //格子上边无障碍物，dp为1
            dp[i][0] = 1;   
        }  
  
        // 从第二行第二列开始计算每个格子的路径数  
        for (int i = 1; i < obstacleGrid.length; i++) {  
            for (int j = 1; j < obstacleGrid[0].length; j++) {  
                // 如果当前格子不是障碍物，则路径数为0 ，是障碍物dp不变（为0） 
                if (obstacleGrid[i][j] != 1) {  
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
                } 
            }  
        }  
  
        // 返回右下角格子的路径数，即从左上角到右下角的唯一路径数  
        return dp[dp.length - 1][dp[0].length - 1];  
    }  
}

343.整数拆分

343. 整数拆分

中等

提示

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 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数组（dp table）以及下标的含义

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

dp[i]的定义将贯彻整个解题过程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

确定递推公式

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

其实可以从1遍历j，然后有两种渠道得到dp[i].

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

一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。

那有同学问了，j怎么就不拆分呢？

j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。那么从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) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。

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

那么在取最大值的时候，为什么还要比较dp[i]呢？

因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。

dp的初始化

严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。

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

这是无解的。

这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！

确定遍历顺序

确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

所以遍历顺序为：

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开始的话，那么让拆分一个数拆个0，求最大乘积就没有意义了。

j的结束条件是 j < i - 1 ，其实 j < i 也是可以的，不过可以节省一步，例如让j = i - 1，的话，其实在 j = 1的时候，这一步就已经拆出来了，重复计算，所以 j < i - 1

至于 i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

举例推导dp数组

举例当n为10的时候，dp数组里的数值，如下：

class Solution {  
    public int integerBreak(int n) {  
        // 创建一个动态规划数组，dp[i] 表示将正整数 i 拆分后得到的最大乘积  
        int[] dp = new int[n + 1];  
          
        // 初始化基础情况，将正整数2拆分只有一个拆分方式即2本身，因此乘积为1  
        dp[2] = 1;  
          
        // 从3开始遍历到n，计算每个数的最大乘积  
        for (int i = 3; i <= n; i++) {  
            // 对于每个数i，遍历所有可能的拆分方式j  
            for (int j = 1; j <= i; j++) {  
                // 计算当前拆分方式的乘积，有两种可能：  
                // 1. 直接将j和(i-j)相乘  
                // 2. 将j与剩下的数(i-j)拆分后的最大乘积相乘  
                // 取两种可能中的较大值更新dp[i]  
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));  
            }  
        }  
          
        // 返回正整数n拆分后的最大乘积  
        return dp[n];  
    }  
}

96.不同的二叉树

96. 不同的二叉搜索树

相关标签

相关企业

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

了解了二叉搜索树之后，我们应该先举几个例子，画画图，看看有没有什么规律，如图：

n为1的时候有一棵树，n为2有两棵树，这个是很直观的。

来看看n为3的时候，有哪几种情况。

当1为头结点的时候，其右子树有两个节点，看这两个节点的布局，是不是和 n 为2的时候两棵树的布局是一样的啊！

（可能有同学问了，这布局不一样啊，节点数值都不一样。别忘了我们就是求不同树的数量，并不用把搜索树都列出来，所以不用关心其具体数值的差异）

当3为头结点的时候，其左子树有两个节点，看这两个节点的布局，是不是和n为2的时候两棵树的布局也是一样的啊！

当2为头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！

发现到这里，其实我们就找到了重叠子问题了，其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。

思考到这里，这道题目就有眉目了。

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数组（dp table）以及下标的含义

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。

确定递推公式

在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当于是头结点的元素，从1遍历到i为止。

所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

dp数组如何初始化

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

那么dp[0]应该是多少呢？

从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。

从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。

所以初始化dp[0] = 1

确定遍历顺序

首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。

那么遍历i里面每一个数作为头结点的状态，用j来遍历。

代码如下：

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

举例推导dp数组

n为5时候的dp数组状态如图：

当然如果自己画图举例的话，基本举例到n为3就可以了，n为4的时候，画图已经比较麻烦了。

我这里列到了n为5的情况，是为了方便大家 debug代码的时候，把dp数组打出来，看看哪里有问题。文章来源地址https://www.toymoban.com/news/detail-841170.html

class Solution {  
    public int numTrees(int n) {  
        // 创建一个动态规划数组dp，dp[i]表示由1到i这些整数能构成的不同二叉搜索树的个数  
        int[] dp = new int[n + 1];  
        // 初始化dp数组，空树和只有一个节点的树都只有1种情况  
        dp[0] = 1;  
        dp[1] = 1;  
          
        // 从2开始遍历到n，计算每个数作为根节点时的不同二叉搜索树的个数  
        for(int i = 2; i <= n; i++){  
            // 对于每个i，枚举1到i之间的每个数j作为根节点  
            for(int j = 1; j <= i; j++){  
                // 当j作为根节点时，左子树由1到j-1构成，右子树由j+1到i构成  
                // 左子树和右子树分别可以构成dp[j-1]和dp[i-j]个不同的二叉搜索树  
                // 因此，以j为根节点的不同二叉搜索树的个数为左子树个数乘以右子树个数  
                // 累加所有以不同数为根节点的情况，得到dp[i]  
                dp[i] += dp[j - 1] * dp[i - j];  
            }  
        }  
        // 返回由1到n这些整数能构成的不同二叉搜索树的个数  
        return dp[n];  
    }  
}

到了这里，关于代码随想录 动态规划-基础题目的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！