代码随想录第29天：动态规划2

一、不同路径（Leetcode 62）

1. 确定dp数组以及下标的含义：从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径
2. 确定递推公式：想要求dp[i][j]，只能从dp[i - 1][j] 和 dp[i][j - 1]两个方向推导出来。     

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

3. dp数组如何初始化：由于只能向右或向下走，所以dp[0][j] = 1, dp[i][0] = 1
4. 确定遍历顺序：从前往后遍历
5. 举例推导dp数组

class Solution:def uniquePaths(self, m: int, n: int) -> int:# 创建一个 m 行 n 列的二维 dp 数组，初始值都为 0dp = [[0]*n for _ in range(m)]# 第一列的所有位置都可以从上方到达，所以将其初始化为 1for i in range(m):dp[i][0] = 1# 第一行的所有位置都可以从左方到达，所以将其初始化为 1for j in range(n):dp[0][j] = 1# 从第二行和第二列开始，计算每个位置的路径数for i in range(1, m):for j in range(1, n):# 每个位置的路径数等于上方位置的路径数 + 左侧位置的路径数dp[i][j] = dp[i - 1][j] + dp[i][j - 1]# 返回右下角的位置，表示从左上角到右下角的不同路径数return dp[m - 1][n - 1]

二、不同路径II（Leetcode 63）

与路径I相比，这题引入了障碍设置。在上题的基础上添加限制，初始化时，第一行和第一列遇到障碍，则障碍后的格子都无法到达，直接break跳过；在第一行第一列的右下方出现障碍，则continue跳过。

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:# 获取网格的行数和列数m = len(obstacleGrid)n = len(obstacleGrid[0])# 创建一个大小为 m 行 n 列的 dp 数组，初始化为 0dp = [[0] * n for _ in range(m)]# 如果起点或终点有障碍物，直接返回 0，表示无法到达if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:return 0# 初始化第一列，如果某个位置是障碍物，则后续位置都无法到达for i in range(m):if obstacleGrid[i][0] == 0:dp[i][0] = 1else:break  # 如果遇到障碍物，后面的所有位置都不能到达# 初始化第一行，如果某个位置是障碍物，则后续位置都无法到达for j in range(n):if obstacleGrid[0][j] == 0:dp[0][j] = 1else:break  # 如果遇到障碍物，后面的所有位置都不能到达# 通过动态规划计算每个位置的路径数for i in range(1, m):for j in range(1, n):# 如果当前格子有障碍物，则跳过if obstacleGrid[i][j] == 1:continue# 如果没有障碍物，则当前位置的路径数等于上方和左侧的路径数之和dp[i][j] = dp[i - 1][j] + dp[i][j - 1]# 返回右下角位置的路径数，即到达终点的路径数return dp[m - 1][n - 1]

三、整数拆分（Leetcode 343）

1.确定dp数组以及下标的含义：拆分数字i，可以得到的最大乘积为dp[i]

2.确定递推公式：

(1). dp[i] = j * (i - j)， 拆分为2个数

(2). dp[i] = j * dp[i - j]，拆分为3个以上的数

为什么不拆分 j 呢？

因为j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过。

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

3.dp数组如何初始化：i = 0 和 1 无意义， dp[0]= 0, dp[1] = 0, dp[2] = 1

4.确定遍历顺序：从前往后遍历

5.举例推导dp数组

class Solution:def integerBreak(self, n: int) -> int:dp = [0] * (n + 1)dp[0], dp[1], dp[2] = 0, 0, 1  # 0 和 1 没有有效的拆分，2 只有拆分成 1 + 1 最大for i in range(3, n + 1):  # 从 3 开始，因为 1 和 2 已经初始化过for j in range(1, i // 2 + 1):  # j 从 1 到 i//2，避免重复计算dp[i] = max(dp[i], j * (i - j), j * dp[i - j])  # 计算最大乘积return dp[n]  # 返回最大乘积

细节优化：

由数学知识，当拆分的数字接近时积是最大的，最少拆分为2个数，这两个数分别为i//2 + 1和i//2 - 1，若拆分为3个以上数，拆分出的单个数字则会更小。所以 j 的遍历可以优化为：

 for j in range(1, i // 2 + 1):  # j 从 1 到 i//2，避免重复计算

四、不同的二叉搜索树（Leetcode 96）

1.确定dp数组以及下标的含义：dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

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

2.确定递推公式：以n = 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]

当n = i 时：

        dp[i] += dp[ 以j为头结点左子树节点数量 ] * dp[ 以j为头结点右子树节点数量 ]

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

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

3.dp数组如何初始化：初始化，只需要初始化dp[0]，初始化dp[0] = 1

4.确定遍历顺序：遍历i里面每一个数作为头结点的状态，用j来遍历。

5.举例推导dp数组

class Solution:def numTrees(self, n: int) -> int:# 初始化 dp 数组，其中 dp[i] 表示有 i 个节点的不同二叉搜索树的数量dp = [0] * (n + 1)dp[0], dp[1] = 1, 1  # 基础情况：0个节点和1个节点时都有1种构造方式# 从 2 到 n 计算每个节点数的不同二叉搜索树数量for i in range(2, n + 1):for j in range(1, i + 1):# 对于每个可能的根节点 j，左子树有 j-1 个节点，右子树有 i-j 个节点dp[i] += dp[j - 1] * dp[i - j]# 返回给定节点数 n 时的不同二叉搜索树数量return dp[n]