跟随carl代码随想录刷题
语言：python

62. 中等不同路径

题目：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
👉示例1：

输入：m = 3, n = 7
输出：28
👉示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

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

题目分析

动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义
   • dp[i][j]表示从(0, 0)出发，到达(i, j)共有 d[i][j]种路径
2. ⭐️确定状态转移公式（递推公式）
   • dp[i][j] = dp[i-1][j] + dp[i][j-1] # 包括两个方向
3. dp数组如何初始化
   • dp[i][0] = 1
   • dp[0][j] = 1
4. 确定遍历顺序
   • 从左到右一层一层遍历
5. 举例推导dp数组

完整代码如下

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 全部初始化为1
        dp = [[1 for i in range(n)] for j in range(m)]

        # 因为已经初始化过了，所以遍历从索引`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]  # 因为数组的索引是从0开始的，所以结束索引为`m-1``n-1`

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

题目分析——有障碍物

动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义
   • dp[i][j]表示从(0, 0)出发，到达(i, j)共有 d[i][j]种路径
2. ⭐️确定状态转移公式（递推公式）
   • 当(i, j)，没有障碍时才进行推导：if obstacleGrid[i][j] == 0:
   • dp[i][j] = dp[i-1][j] + dp[i][j-1] # 包括两个方向
3. dp数组如何初始化
   • 当路径没有障碍时obstacleGrid[i][0] != 1：
     • dp[i][0] = 1 # 从(0, 0)到(i, 0)的路径只有一条
   • 当路径没有障碍时obstacleGrid[0][i] != 1：
     • dp[0][i] = 1
4. 确定遍历顺序
   • 从左到右一层一层遍历
   • 最后一个元素为dp[-1][-1]
5. 举例推导dp数组

完整代码如下

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 构造一个dp table
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])
        dp = [[0 for _ in range(col)] for _ in range(row)]

        # 第一个格子有可能出现障碍哦
        dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0
        if dp[0][0] == 0: return 0  # 如果第一个格子就是障碍，return 0

        # 第一行
        for i in range(1, col):
            if obstacleGrid[0][i] != 1:
                dp[0][i] = dp[0][i-1]

        # 第一列
        for i in range(1, row):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]
        # print(dp)

        for i in range(1, row):
            for j in range(1, col):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]  # 这种写法很妙

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。

题目分析

动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义
   • dp[i]表示分拆数字i，可以得到的最大乘积为dp[i]
2. ⭐️确定状态转移公式（递推公式）
   • dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)) # 包括两个方向
3. dp数组如何初始化
   • dp[2] = 1 # 初始化dp[0]和dp[1]没有意义
4. 确定遍历顺序
   • 从前向后遍历
5. 举例推导dp数组

完整代码如下

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1

        for i in range(3, n + 1):
            # 假设对正整数 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]
            for j in range(1, i - 1):
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        return dp[n]

96. 困难不同的二叉搜索树

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

题目分析

动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义
   • dp[i]表示：1到i为节点组成的二叉搜索树的个数为dp[i]
2. ⭐️确定状态转移公式（递推公式）
   • dp[i] += dp[j - 1] * dp[i - j] # j-1是以j为头节点的左子树的节点数量，i-j为以j为头节点的右子树的节点数量
3. dp数组如何初始化
   • dp[0] = 1 # 初始化dp[0]
4. 确定遍历顺序
   • 从前向后遍历
5. 举例推导dp数组

完整代码如下

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[-1]