本文共 2813 字，大约阅读时间需要 9 分钟。
一个机器人位于一个 m x n 网格的左上角，起始点标记为“Start”。机器人每次只能向下或者向右移动一步，目标是到达网格的右下角“Finish”。问总共有多少条不同的路径？
示例：输入：m = 3, n = 7，输出：28。
问题分析
机器人每次只能向下或向右移动一步，因此到达网格右下角的路径数可以通过组合数学计算。具体来说，机器人需要向右移动 n-1 次，向下移动 m-1 次，总路径数为组合数 C(m+n-2, m-1) 或 C(m+n-2, n-1)。动态规划方法
定义状态 dp[i][j] 为从左上角到 (i, j) 的不同路径数。状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]，边界条件为 dp[0][j] = 1 和 dp[i][0] = 1。优化方法
使用状态压缩，仅需记录当前行和上一行的值，空间复杂度降至 O(n)。class Solution: def uniquePaths(self, m: int, n: int) -> int: if m == 0 or n == 0: return 0 dp = [[0] * n for _ in range(m)] for i in range(m): dp[i][0] = 1 for 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[-1][-1]
一个机器人位于一个 m x n 网格的左上角，起始点标记为“Start”。网格中有障碍物，障碍物和空位置分别用 1 和 0 表示。问从左上角到右下角的不同路径数？
示例：障碍物Grid = [[0,0,0],[0,1,0],[0,0,0]]，输出：2。
动态规划方法
定义 dp[i][j] 为从 (0, 0) 到 (i, j) 的不同路径数。状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]，但如果当前格子为障碍物，则路径数为 0。初始条件
dp[0][j] = 1 和 dp[i][0] = 1，前提是对应的格子不是障碍物。优化方法
可以记录上一行和当前行的值，空间复杂度为 O(n)。class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: if not obstacleGrid or not obstacleGrid[0]: return 0 m = len(obstacleGrid) n = len(obstacleGrid[0]) dp = [[0] * n for _ in range(m)] for i in range(m): dp[i][0] = 1 if obstacleGrid[i][0] == 0 else 0 for j in range(n): dp[0][j] = 1 if obstacleGrid[0][j] == 0 else 0 for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] == 1: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
给定一个包含非负整数的 m x n 网格 grid，从左上角到右下角的路径使得路径上的数字总和最小。
示例：grid = [[1,3,1],[1,5,1],[4,2,1]]，输出：7。
动态规划方法
定义 dp[i][j] 为从左上角到 (i, j) 的最小路径和。状态转移方程为 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。初始条件
dp[0][j] = dp[0][j-1] + grid[0][j]，dp[i][0] = dp[i-1][0] + grid[i][0]。优化方法
可以直接修改原矩阵，空间复杂度为 O(1)。class Solution: def minPathSum(self, grid: List[List[int]]) -> int: if not grid or not grid[0]: return 0 rows = len(grid) cols = len(grid[0]) for i in range(rows): for j in range(cols): if i == j == 0: continue elif i == 0: grid[i][j] = grid[i][j-1] + grid[i][j] elif j == 0: grid[i][j] = grid[i-1][j] + grid[i][j] else: grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j] return grid[-1][-1]
转载地址：http://qugh.baihongyu.com/