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

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0] * n for _ in range(m)]for i in range(m):for j in range(n):if i == 0 or j == 0:if i == 0 and j == 0:dp[i][j] = 1elif i == 0:dp[i][j] = dp[i][j - 1]else:dp[i][j] = dp[i - 1][j]else:dp[i][j] = dp[i][j - 1] + dp[i - 1][j]return dp[i][j]

直接生成dp数组，根据题目要求遍历，当某一点$[i,j$]可达的时候，必然可以到达$[i-1,j]$和$[i,j-1]$，路径数为二者之和，代码增加对边界的判断就行。
参考代码

class Solution:def uniquePaths(self, m: int, n: int) -> int:# 创建一个二维列表用于存储唯一路径数dp = [[0] * n for _ in range(m)]# 设置第一行和第一列的基本情况for i in range(m):dp[i][0] = 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]

第一行和第一列可以事先声明。

class Solution:def uniquePaths(self, m: int, n: int) -> int:# 创建一个二维列表用于存储唯一路径数dp = [[0] * n for _ in range(m)]# 设置第一行和第一列的基本情况for i in range(m):dp[i][0] = 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]

tips:求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。

数论方法，到达$[m,n]$，共需要走$m+n-2$步，其中向右$n-1$步向下$m-1$步。转化为，m + n - 2个不同的数，随便取m - 1个数，有几种取法
$$c_{m+n-2}^{m-1}$$

63. 不同路径 II

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid)n = len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]for i in range(m):for j in range(n):if obstacleGrid[i][j] == 1:dp [i][j] = 0else:if i == 0 or j == 0:if i == 0 and j == 0:dp[i][j] = 1elif i == 0:dp[i][j] = dp[i][j - 1]else:dp[i][j] = dp[i - 1][j]else:dp[i][j] = dp[i][j - 1] + dp[i - 1][j]return dp[i][j]

和上题一样，增加一个障碍物判断，遇到障碍物时候，无法到达目标所以该位置dp值是0。

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。

class Solution:def integerBreak(self, n: int) -> int:dp = [0]* (n+1)dp[1] = 1#初始化for i in range(2,n+1):#dp[n]记录n的值，所以长度是n+1res = 0for j in range(1,i):#从1到i-1分割res = max(res,j * dp[i-j],j*(i-j))dp[i] = resreturn dp[n]

维护dp数组，代表正整数n拆分后的最大乘积。

• 假设k=2时，拆分正整数$n$乘积达到最大值，则$j$从$2$遍历到$n-1$，最大值在$(n-j)\ast j$之间。
• 假设k=3时，拆分正整数$n$乘积达到最大值，从正整数拆分一个$i$后，问题转化为$n-i$拆分2个值后最大值，$dp[n-i]$已经维护。最大值为$i\ast dp[n-i]$，遍历$i$返回最大值。
• k=3,k=4以此类推

参考代码

• 只初始化$dp[2]=1$，从$dp[i]$的定义来说，拆分数字$2$，得到的最大乘积是$1$,$dp[1]$,$dp[0]$数值无意义，初始化只是方便计算，不好解释。
• 拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值

class Solution:# 假设对正整数 i 拆分出的第一个正整数是 j（1 <= j < i），则有以下两种方案：# 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)# 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]def integerBreak(self, n):dp = [0] * (n + 1)   # 创建一个大小为n+1的数组来存储计算结果dp[2] = 1  # 初始化dp[2]为1，因为当n=2时，只有一个切割方式1+1=2，乘积为1# 从3开始计算，直到nfor i in range(3, n + 1):# 遍历所有可能的切割点for j in range(1, i // 2 + 1):# 计算切割点j和剩余部分(i-j)的乘积，并与之前的结果进行比较取较大值dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)return dp[n]  # 返回最终的计算结果

贪心算法每次拆成n个3，如果剩下是4，则保留4，然后相乘，需要数学证明，暂时不用掌握。

class Solution:def integerBreak(self, n):if n == 2:  # 当n等于2时，只有一种拆分方式：1+1=2，乘积为1return 1if n == 3:  # 当n等于3时，只有一种拆分方式：2+1=3，乘积为2return 2if n == 4:  # 当n等于4时，有两种拆分方式：2+2=4和1+1+1+1=4，乘积都为4return 4result = 1while n > 4:result *= 3  # 每次乘以3，因为3的乘积比其他数字更大n -= 3  # 每次减去3result *= n  # 将剩余的n乘以最后的结果return result

96. 不同的二叉搜索树

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

示例 1：
输入：n = 3
输出：5

示例 2：
输入：n = 1
输出：1

class Solution:def numTrees(self, n: int) -> int:dp =[0]*(n+1)dp[0]=1dp[1]=1for i in range(2,n+1):for j in range(1,i+1):#j树节点，小于j和大于jdp[i]+=dp[j-1] * dp[i-j]return dp[n]

以$n=3$为例:

• 1做根节点，左边小于1的节点有$0$个，右边大于1的节点有$2$个，返回$dp[0]\ast dp[2]$
• 2做根节点，左边小于1的节点有$1$个，右边大于1的节点有$1$个，返回$dp[1]\ast dp[1]$
• 3做根节点，左边小于1的节点有$2$个，右边大于1的节点有$0$个，返回$dp[2]\ast dp[0]$
  根节点遍历完毕，求和。

参考代码

class Solution:def numTrees(self, n: int) -> int:dp = [0] * (n + 1)  # 创建一个长度为n+1的数组，初始化为0dp[0] = 1  # 当n为0时，只有一种情况，即空树，所以dp[0] = 1for i in range(1, n + 1):  # 遍历从1到n的每个数字for j in range(1, i + 1):  # 对于每个数字i，计算以i为根节点的二叉搜索树的数量dp[i] += dp[j - 1] * dp[i - j]  # 利用动态规划的思想，累加左子树和右子树的组合数量return dp[n]  # 返回以1到n为节点的二叉搜索树的总数量