带障碍网格中允许左右下移动的最大1数量路径求解问题

这个问题的核心突破口是移动方向限制：仅允许左、右、下三个方向，无法向上移动，因此行号是单调不减的，走到第i行后永远不会回到i-1及以上的行，完全避免了跨行的重复访问问题。
同一行内移动时，由于不能重复经过单元格，从上方进入当前行的某位置j后，只能选择两种路径：要么一直向左走到头，要么一直向右走到头，不能往返走（否则会重复经过进入点j）。
基于这个特性我们可以用线性动态规划求解：

• 用dp_prev[j]存储上一行第j列可获得的最大1的数量，不可达时设为极小值。
• 对每一行分别计算两个辅助数组：
  • left[j]：进入当前行后仅向右移动，到达j列的最大价值。
  • right[j]：进入当前行后仅向左移动，到达j列的最大价值。
• 当前行每个位置的最大价值为max(left[j], right[j])，直接作为下一轮迭代的dp_prev。
  整个算法时间复杂度为O(mn)，空间复杂度为O(n)，完全适配400*400的网格规模。

def maxPathSum(grid):
    m = len(grid)
    n = len(grid[0])
    INF = float('-inf')
    # 起点或终点是障碍直接返回-1
    if grid[0][0] == 0 or grid[-1][-1] == 0:
        return -1
    
    # 初始化第0行
    left = [INF] * n
    left[0] = grid[0][0]
    for j in range(1, n):
        if grid[0][j] == 0:
            left[j] = INF
        else:
            left[j] = max(left[j], left[j-1] + grid[0][j])
    
    right = [INF] * n
    right[0] = grid[0][0]
    for j in range(n-2, -1, -1):
        if grid[0][j] == 0:
            right[j] = INF
        else:
            right[j] = max(right[j], right[j+1] + grid[0][j])
    
    dp_prev = [max(left[j], right[j]) for j in range(n)]
    
    # 处理剩下的行
    for i in range(1, m):
        # 计算left数组：仅向右走
        left = [INF] * n
        for j in range(n):
            if grid[i][j] == 0 or dp_prev[j] == INF:
                left[j] = INF
            else:
                left[j] = dp_prev[j] + grid[i][j]
        for j in range(1, n):
            if grid[i][j] == 0:
                continue
            left[j] = max(left[j], left[j-1] + grid[i][j])
        
        # 计算right数组：仅向左走
        right = [INF] * n
        for j in range(n):
            if grid[i][j] == 0 or dp_prev[j] == INF:
                right[j] = INF
            else:
                right[j] = dp_prev[j] + grid[i][j]
        for j in range(n-2, -1, -1):
            if grid[i][j] == 0:
                continue
            right[j] = max(right[j], right[j+1] + grid[i][j])
        
        # 更新当前行的dp数组
        dp_prev = [max(left[j], right[j]) for j in range(n)]
    
    return dp_prev[-1] if dp_prev[-1] != INF else -1

• 若起点(0,0)或终点(m-1,n-1)本身是障碍物，直接返回-1。
• 第一行没有上一行，只能从(0,0)开始初始化左右数组。
• 最终如果终点的取值仍为初始极小值，说明不存在合法路径，返回-1。

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