第一题、62.不同路径
用 f(i,j) 表示从左上角走到 (i,j) 的路径数量，其中 i 和 j 的范围分别是 [0,m) 和 [0,n)。
由于每一步只能从向下或者向右移动一步，因此要想走到 (i,j)，如果向下走一步，那么会从 (i−1,j) 走过来；如果向右走一步，那么会从 (i,j−1) 走过来。因此动态规划转移方程：
f(i,j)=f(i−1,j)+f(i,j−1)
需要注意的是，如果 i=0，那么 f(i−1,j) 并不是一个满足要求的状态，需要忽略这一项；同理，如果 j=0，那么 f(i,j−1) 并不是一个满足要求的状态，需要忽略这一项。
初始条件为 f(0,0)=1，即从左上角走到左上角有一种方法。
最终的答案即为 f(m−1,n−1)。
为了方便代码编写，可以将所有的 f(0,j) 以及 f(i,0) 都设置为边界条件，它们的值均为 1。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 初始化一个二维数组f，大小为m行n列
# 第一行全为1，表示从起点到第一行每个位置的路径数都为1
# 其余行的第一列为1，表示从起点到第一列每个位置的路径数也为1
f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
# 打印初始化后的f，用于调试
print(f)
# 从第二行（索引1）和第二列（索引1）开始遍历整个二维数组
for i in range(1, m):
for j in range(1, n):
# 当前格子的路径数等于上方格子的路径数加左边格子的路径数
f[i][j] = f[i - 1][j] + f[i][j - 1]
# 返回右下角格子的路径数，即从起点到终点的不同路径数
return f[m - 1][n - 1]
由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 初始化一个一维数组f，大小为n，用于存储当前行每个位置的路径数
f = [1] * n
# 从第2行（索引1）开始遍历，计算每一行的路径数
for i in range(1, m):
# 从第2列（索引1）开始遍历，更新当前行每个位置的路径数
for j in range(1, n):
# 当前列的路径数等于左边格子的路径数加上原来的路径数
f[j] += f[j - 1]
# 返回最后一列的路径数，即从起点到终点的不同路径数
return f[n - 1]
时间复杂度：O(mn)。
空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于交换行列的值并不会对答案产生影响，因此总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。
方法二、组合数学
从左上角到右下角的过程中，需要移动 m+n−2 次，其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数，即组合数：
[
C_{m+n-2}^{m-1} = \binom{m+n-2}{m-1} = \frac{(m-1)!}{(m+n-2)(m+n-3)\cdots n} = \frac{(m-1)!(n-1)!}{(m+n-2)!}
]
因此直接计算出这个组合数即可。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 直接使用组合公式计算从左上角到右下角的不同路径数
# 公式为C(m+n-2, n-1)，表示在(m+n-2)步中选择(n-1)步向下或者(m-1)步向右的组合数
return comb(m + n - 2, n - 1)
时间复杂度：O(m)。由于交换行列的值并不会对答案产生影响，因此总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。
空间复杂度：O(1)。
第二题、63.不同路径2
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 获取网格的行数n和列数m
n, m = len(obstacleGrid), len(obstacleGrid[0])
# 初始化一维数组f，用于存储当前行的路径数
f = [0] * m
# 如果起点没有障碍物，则将f[0]设置为1
f[0] = 1 if obstacleGrid[0][0] == 0 else 0
# 遍历每一行
for i in range(n):
# 遍历当前行的每一列
for j in range(m):
# 如果当前位置有障碍物，则路径数设为0
if obstacleGrid[i][j] == 1:
f[j] = 0
# 否则，如果可以从左边的格子到达当前格子，则更新路径数
elif j > 0 and obstacleGrid[i][j - 1] == 0:
f[j] += f[j - 1]
# 返回最后一列的路径数，即从起点到终点的不同路径数
return f[-1]
时间复杂度：O(nm)，其中 n 为网格的行数，m 为网格的列数。只需要遍历所有网格一次即可。
空间复杂度：O(m)。利用滚动数组优化，可以只用 O(m) 大小的空间来记录当前行的 f 值。
第三题、980题.不同路径3
方法一、回溯
按照要求，假设矩阵中有 n 个 0，那么一条合格的路径，是长度为 (n+1)，由 1 起始，结束于 2，不经过 −1，且每个点只经过一次的路径。要求出所有的合格的路径，可以采用回溯法，定义函数 dfs，表示当前 grid 状态下，从点 (i,j) 出发，还要经过 n 个点，走到终点的路径条数。到达一个点时，如果当前的点为终点，且已经经过了 (n+1) 个点，那么就构成了一条合格的路径，否则就不构成。如果当前的点不为终点，则将当前的点标记为 −1，表示这条路径以后不能再经过这个点，然后继续在这个点往四个方向扩展，如果不超过边界且下一个点的值为 0 或者 2，则表示这条路径可以继续扩展。探测完四个方向后，需要将当前的点的值改为原来的值。将四个方向的合格路径求和，即为当前状态下合格路径的条数。最终需要返回的是，grid 在初始状态下，从起点出发，需要经过 (n+1) 个点的路径条数。
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
# 获取网格的行数r和列数c
r, c = len(grid), len(grid[0])
# 初始化起点坐标si, sj和需要经过的空格数量n
si, sj, n = 0, 0, 0
# 遍历网格，寻找起点并计算需要经过的空格数量
for i in range(r):
for j in range(c):
if grid[i][j] == 0:
n += 1 # 计算需要经过的空格数量
elif grid[i][j] == 1:
n += 1 # 起点也计入空格数量
si, sj = i, j # 记录起点位置
# 深度优先搜索函数，寻找所有从起点到终点的路径
def dfs(i: int, j: int, n: int) -> int:
# 如果到达终点并且所有空格都已经经过，返回1表示找到一条有效路径
if grid[i][j] == 2:
if n == 0:
return 1
return 0
# 记录当前位置的值，并将其标记为已访问
t = grid[i][j]
grid[i][j] = -1
# 初始化路径计数器res
res = 0
# 遍历四个方向：上、下、左、右
for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
ni, nj = i + di, j + dj
# 检查新位置是否在网格范围内且未访问过，或者是终点
if 0 <= ni < r and 0 <= nj < c and grid[ni][nj] in [0, 2]:
# 递归调用DFS，探索新位置，减少一个空格数量
res += dfs(ni, nj, n - 1)
# 回溯，将当前位置的值恢复
grid[i][j] = t
# 返回找到的路径总数
return res
# 从起点开始执行深度优先搜索，返回所有有效路径的总数
return dfs(si, sj, n)
方法二、记忆化搜索 + 状态压缩
方法一的回溯函数，即使在 i,j,n 都相同的情况下，函数的返回值也会不同，因为路径经过的点不同，导致当前情况下 grid 的状态也不同。因此，可以将grid 的状态放入函数的输入参数，从而用记忆化搜索来降低时间复杂度。
用一个二进制数字 st 来表示路径还未经过的点（初始状态下为所有值为 0 的点和终点），点的坐标需要和二进制数字的位一一对应。定义函数 dp，输入参数为当前坐标 i,j 和未经过的点的二进制集合 st，返回值即为从点 (i,j) 出发，经过 st 代表的点的集合，最终到达终点的路径的条数。如果当前点为终点且剩下没有未经过的点，那么当前的返回值即为 1，否则为 0。如果当前的点不为终点，则需要探索四个方向，如果接下来的点在边界内且还未经过（用按位和操作判断），则需要走到那个点并且将那个点的坐标从未经过的点的集合中去掉（用按位异或操作）。将四个方向的合格路径求和，即为当前状态下合格路径的条数。最终需要返回的是，从起点出发，为经过的点的集合为所有值为 0 的点和终点的路径条数。函数调用过程中采用了记忆化搜索，每个状态最多只会被计算一次。
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
# 获取网格的行数r和列数c
r, c = len(grid), len(grid[0])
# 初始化起点位置si, sj和状态位st，用于表示需要经过的所有空格
si, sj, st = 0, 0, 0
# 遍历网格，寻找起点并初始化状态位
for i in range(r):
for j in range(c):
# 如果当前格子是空格或终点，则将其对应的位置标记到st中
if grid[i][j] in [0, 2]:
st |= (1 << (i * c + j))
# 如果当前格子是起点，则记录起点的位置
elif grid[i][j] == 1:
si, sj = i, j
# 使用LRU缓存的动态规划函数，i和j表示当前所在位置，st表示剩余需要经过的空格状态
@lru_cache(None)
def dp(i: int, j: int, st: int) -> int:
# 如果到达终点并且所有空格都已经经过，返回1表示找到一条有效路径
if grid[i][j] == 2:
if st == 0:
return 1
return 0
# 初始化路径计数器res
res = 0
# 遍历四个方向：上、下、左、右
for di, dj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
ni, nj = i + di, j + dj
# 检查新位置是否在网格范围内且未访问过
if 0 <= ni < r and 0 <= nj < c and (st & (1 << (ni * c + nj))) > 0:
# 递归调用动态规划函数，更新状态位并探索新位置
res += dp(ni, nj, st ^ (1 << (ni * c + nj)))
# 返回找到的路径总数
return res
# 从起点开始执行动态规划，返回所有有效路径的总数
return dp(si, sj, st)
第四题、64.最小路径和
方法一、动态规划
由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。
当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。
最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# 如果网格为空或第一行为空，返回0
if not grid or not grid[0]:
return 0
# 获取网格的行数和列数
rows, columns = len(grid), len(grid[0])
# 初始化一个与网格大小相同的二维数组dp，用于存储到达每个位置的最小路径和
dp = [[0] * columns for _ in range(rows)]
# 设置起点的路径和为起点的值
dp[0][0] = grid[0][0]
# 处理第一列的路径和，累加上方格子的路径和
for i in range(1, rows):
dp[i][0] = dp[i - 1][0] + grid[i][0]
# 处理第一行的路径和，累加左边格子的路径和
for j in range(1, columns):
dp[0][j] = dp[0][j - 1] + grid[0][j]
# 处理其余位置的路径和，选择从上方或左边到达当前格子的最小路径和
for i in range(1, rows):
for j in range(1, columns):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
# 返回终点的路径和，即从起点到终点的最小路径和
return dp[rows - 1][columns - 1]
时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。
空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp，和网格大小相同。
空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。
