求由0和1组成的矩阵中从左上角到右下角的路径总数

这是个经典的带障碍的网格路径计数问题，我来分享几种实用的解法，从基础实现到空间优化版本都有：

我们可以用动态规划来解决这个问题，核心是定义状态和状态转移方程：

• 定义dp[i][j]为从左上角(0,0)走到(i,j)的有效路径总数。
• 状态转移：
  • 如果当前单元格grid[i][j]是0（不可通行），那么dp[i][j] = 0，因为没有路径能走到这里。
  • 如果当前单元格是1（可通行），那么dp[i][j] = dp[i-1][j] + dp[i][j-1]——也就是从上方单元格下来的路径数，加上从左方单元格过来的路径数之和。
• 边界处理：
  • 第一行的单元格只能从左边走过来，所以如果grid[0][j]是1，dp[0][j] = dp[0][j-1]；否则为0。
  • 第一列的单元格只能从上方走下来，同理如果grid[i][0]是1，dp[i][0] = dp[i-1][0]；否则为0。
  • 起点(0,0)如果是0，直接返回0，因为根本无法出发。

这是最直观的实现方式，空间复杂度为O(M*N)，适合理解逻辑：

def count_paths(grid):
    # 特殊情况：起点或终点不可通行，直接返回0
    if not grid or grid[0][0] == 0 or grid[-1][-1] == 0:
        return 0
    
    m, n = len(grid), len(grid[0])
    # 初始化DP数组
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1  # 起点有1条路径
    
    # 填充第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] if grid[0][j] == 1 else 0
    
    # 填充第一列
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] if grid[i][0] == 1 else 0
    
    # 填充剩余单元格
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            else:
                dp[i][j] = 0
    
    return dp[-1][-1]

观察状态转移方程可以发现，计算dp[i][j]只需要上一行的dp[i-1][j]和当前行已经计算好的dp[i][j-1]，所以我们可以用一维数组来优化空间，把空间复杂度降到O(min(M,N))：

def count_paths_optimized(grid):
    if not grid or grid[0][0] == 0 or grid[-1][-1] == 0:
        return 0
    
    m, n = len(grid), len(grid[0])
    # 选择较小的维度来节省空间，如果列数更多，转置矩阵
    if n > m:
        return count_paths_optimized([list(col) for col in zip(*grid)])
    
    dp = [0] * n
    dp[0] = 1  # 起点初始化
    
    # 填充第一行
    for j in range(1, n):
        dp[j] = dp[j-1] if grid[0][j] == 1 else 0
    
    # 填充剩余行
    for i in range(1, m):
        # 先处理当前行的第一个元素
        dp[0] = dp[0] if grid[i][0] == 1 else 0
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[j] = dp[j] + dp[j-1]  # dp[j]是上一行的值，dp[j-1]是当前行左边的值
            else:
                dp[j] = 0
    
    return dp[-1]

• 题目提到结果可能很大，你可以在每次路径数相加后对一个大数取模，比如常用的10^9 + 7，只需要在代码里把dp[i][j] = ...改成dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD即可（记得先定义MOD = 10**9 +7）。
• 递归+记忆化的方式也能解决，但对于大矩阵可能会出现栈溢出的问题，所以动态规划是更稳妥的选择。

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