Python带障碍网格路径计数代码优化求助：计算左下到右上路径数

咱们先明确问题核心规则：从网格左下角（最后一行第一列，值为0）走到右上角（第一行最后一列，值为0），只能移动到值为0的单元格，默认移动方向为向上或向右（这是这类路径问题的常规设定，若有其他方向需求可随时调整）。

一、基础动态规划解法 #

动态规划是这类路径计数问题的标准解法，核心思路是用dp[i][j]记录从起点到单元格(i,j)的可行路径总数。

实现步骤： #

1. 边界校验：如果起点或终点本身是障碍（值为1），直接返回0，因为不存在可行路径。
2. 初始化DP数组：起点dp[rows-1][0] = 1（只有1种方式到达起点自身）。
3. 填充DP数组：
   • 最后一行的单元格只能从左侧移动而来，所以依次向左到右填充。
   • 第一列的单元格只能从下方移动而来，所以依次从下到上填充。
   • 其他单元格：若当前单元格是0，则路径数等于上方单元格路径数 + 左方单元格路径数；若为1（障碍），则路径数为0。
4. 返回结果：终点dp[0][cols-1]的值就是总可行路径数。

基础版代码： #

def count_paths(grid):
    if not grid or grid[-1][0] == 1 or grid[0][-1] == 1:
        return 0
    rows, cols = len(grid), len(grid[0])
    dp = [[0]*cols for _ in range(rows)]
    
    # 初始化起点路径数
    dp[-1][0] = 1
    
    # 填充最后一行（仅能从左侧来）
    for j in range(1, cols):
        if grid[-1][j] == 0:
            dp[-1][j] = dp[-1][j-1]
    
    # 填充第一列（仅能从下方来）
    for i in range(rows-2, -1, -1):
        if grid[i][0] == 0:
            dp[i][0] = dp[i+1][0]
    
    # 填充剩余单元格
    for i in range(rows-2, -1, -1):
        for j in range(1, cols):
            if grid[i][j] == 0:
                dp[i][j] = dp[i+1][j] + dp[i][j-1]
    
    return dp[0][-1]

# 测试示例网格（转换为二维数组）
sample_grid = [
    [0,1,0,0,0],
    [1,0,0,0,1],
    [0,0,1,0,0],
    [0,0,0,0,0]
]
print(count_paths(sample_grid))  # 输出5，符合预期

# 测试目标大网格（转换为二维数组）
target_grid = [
    [0,0,0,1,0,1,0,1,0,1,0,0],
    [0,0,0,0,1,0,0,1,1,0,0,0],
    [0,0,0,0,0,0,0,0,1,1,1,0],
    [0,0,0,1,0,1,0,0,0,0,0,0]
]
print(count_paths(target_grid))  # 输出8，符合预期

二、优化方案：空间压缩 #

基础DP用了二维数组，其实可以优化为一维数组——因为每个单元格只依赖下方和左方的路径数，我们可以用滚动数组复用空间，大幅降低内存消耗。

优化思路： #

• 用长度等于列数的一维数组dp，先填充最后一行的路径数作为初始值。
• 从倒数第二行向上遍历每一行：
  • 第一列：若当前单元格是障碍则设为0，否则继承下方的路径数。
  • 其他列：若当前单元格是0，则dp[j] = 原dp[j]（下方路径数） + dp[j-1]（左方路径数）；若为障碍则设为0。

优化后代码： #

def count_paths_optimized(grid):
    if not grid or grid[-1][0] == 1 or grid[0][-1] == 1:
        return 0
    rows, cols = len(grid), len(grid[0])
    dp = [0]*cols
    
    # 初始化最后一行路径数
    dp[0] = 1 if grid[-1][0] == 0 else 0
    for j in range(1, cols):
        if grid[-1][j] == 0:
            dp[j] = dp[j-1]
    
    # 向上遍历每一行，更新dp数组
    for i in range(rows-2, -1, -1):
        # 处理第一列
        if grid[i][0] == 1:
            dp[0] = 0
        # 处理剩余列
        for j in range(1, cols):
            if grid[i][j] == 1:
                dp[j] = 0
            else:
                dp[j] += dp[j-1]
    
    return dp[-1]

# 测试示例
print(count_paths_optimized(sample_grid))  # 输出5
# 测试目标网格
print(count_paths_optimized(target_grid))  # 输出8

这个版本的空间复杂度从O(rows*cols)降到了O(cols)，当网格行数远大于列数时，空间节省效果非常明显。

三、替代解法：记忆化递归 #

如果偏好递归的直观逻辑，可以用记忆化搜索避免重复计算相同单元格的路径数。

代码实现： #

def count_paths_recursive(grid):
    if not grid or grid[-1][0] == 1 or grid[0][-1] == 1:
        return 0
    rows, cols = len(grid), len(grid[0])
    memo = {}  # 缓存已计算的单元格路径数
    
    def dfs(i, j):
        # 到达终点，返回1条有效路径
        if i == 0 and j == cols-1:
            return 1
        # 越界或遇到障碍，返回0
        if i < 0 or j >= cols or grid[i][j] == 1:
            return 0
        # 已缓存的结果直接返回
        if (i,j) in memo:
            return memo[(i,j)]
        # 递归计算向上和向右的路径数之和
        res = dfs(i-1, j) + dfs(i, j+1)
        memo[(i,j)] = res
        return res
    
    return dfs(rows-1, 0)

# 测试示例
print(count_paths_recursive(sample_grid))  # 输出5
# 测试目标网格
print(count_paths_recursive(target_grid))  # 输出8

递归的优势是逻辑清晰，但对于超大网格可能会出现栈溢出问题，此时迭代版DP会更稳定。

四、额外注意事项 #

• 移动方向扩展：如果允许其他移动方向（比如向下/向左），只需调整DP或递归中的路径来源判断即可。
• 网格预处理：用户给出的是一维数字串，需要先按行列数分割为二维数组（比如示例20个数字按4行5列拆分）。
• 异常处理：始终先校验起点、终点是否为障碍，避免无效计算。

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