含障碍n×n网格路径计数的自顶向下与自底向上实现

问题规则 #

给定n×n规格的网格，从起点grid[0][0]出发，每次仅可选择向右或向下移动1格，网格中标记为H的位置为障碍物，不可穿越，统计到达终点grid[n-1][n-1]的可行路径总数。

问题示例：

grid = [
    ['.', '.', '.', '.'],
    ['.', '.', '.', 'H'],
    ['.', '.', 'H', '.'],
    ['.', '.', '.', '.']
]

该示例避开所有H从起点走到终点的正确路径数为4。

实现方法1：自顶向下（记忆化递归） #

核心思路是从终点往起点倒推做递归，把「到达(i,j)的路径数」拆成两个子问题的和：从上方(i-1,j)下来的路径数、从左方(i,j-1)右移过来的路径数，同时用缓存存储已经计算过的位置结果，避免重复计算。

• 边界判定规则：
  • 当前坐标越界、或当前位置是障碍物H时，返回0（无合法路径）
  • 当前坐标为起点(0,0)时，返回1（仅存在1种停留起点的方式）
  • 当前坐标的结果已经在缓存中时，直接返回缓存值
• 递推公式：dfs(i,j) = dfs(i-1,j) + dfs(i,j-1)
• 可运行代码：

def count_paths_topdown(grid):
    n = len(grid)
    # 起点或终点本身是障碍物，直接返回0
    if grid[0][0] == 'H' or grid[n-1][n-1] == 'H':
        return 0
    # 初始化记忆化缓存，-1代表未计算
    memo = [[-1 for _ in range(n)] for _ in range(n)]

    def dfs(i, j):
        # 越界/撞障碍物返回0
        if i < 0 or j < 0 or grid[i][j] == 'H':
            return 0
        # 递归到起点返回1
        if i == 0 and j == 0:
            return 1
        # 已计算过直接读缓存
        if memo[i][j] != -1:
            return memo[i][j]
        # 累加两个方向的路径数存入缓存
        memo[i][j] = dfs(i-1, j) + dfs(i, j-1)
        return memo[i][j]

    return dfs(n-1, n-1)

实现方法2：自底向上（动态规划递推） #

核心思路是从起点出发正向递推，维护DP表，其中dp[i][j]表示从起点到达位置(i,j)的合法路径数，先计算边界的第一行、第一列的路径数，再逐行逐列计算所有内部位置的结果，最终DP表右下角的值就是答案。

• 初始化规则：
  • 起点dp[0][0] = 1，若起点为障碍物直接返回0
  • 第一行所有位置：未碰到障碍物时，路径数等于左侧相邻位置的路径数（第一行只能从左侧右移到达）；碰到障碍物后，该行后续位置路径数全为0
  • 第一列所有位置：未碰到障碍物时，路径数等于上方相邻位置的路径数（第一列只能从上方下移到达）；碰到障碍物后，该列后续位置路径数全为0
• 递推公式：当前位置为障碍物时dp[i][j] = 0；当前位置可通行时dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 可运行代码：

def count_paths_bottomup(grid):
    n = len(grid)
    # 起点或终点本身是障碍物，直接返回0
    if grid[0][0] == 'H' or grid[n-1][n-1] == 'H':
        return 0
    dp = [[0 for _ in range(n)] for _ in range(n)]
    dp[0][0] = 1
    # 填充第一行
    for j in range(1, n):
        if grid[0][j] == '.':
            dp[0][j] = dp[0][j-1]
    # 填充第一列
    for i in range(1, n):
        if grid[i][0] == '.':
            dp[i][0] = dp[i-1][0]
    # 填充其余位置
    for i in range(1, n):
        for j in range(1, n):
            if grid[i][j] == 'H':
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n-1][n-1]

效果验证：传入题目给出的示例网格，两个方法的返回结果均为4，符合预期。

内容的提问来源于stack exchange，提问作者Erin Yeh