网格路径统计递归函数中基例返回1的计数逻辑疑问

问题背景 #

给定网格，找出从左上角(0,0)到右下角的所有可行路径，仅允许向下或向右移动，标记为"X"的是不可通行的墙。

示例代码 #

grid = [
  ["O", "O", "X"],
  ["O", "O", "O"],
  ["O", "O", "O"],
]
count_paths(grid) # -> 5

实现代码 #

def count_paths(grid):
  return _count_paths(grid,0,0,{})

def _count_paths(grid,r,c,memo):
  pos = (r,c)
  if pos in memo:
    return memo[pos]
  
  if not 0 <= r <len(grid) or not 0<= c < len(grid[0]) or grid[r][c]=="X":
    return 0
  
  if r == len(grid)-1 and c == len(grid[0])-1:
    return 1
  
  down_count = _count_paths(grid, r+1,c,memo)
  right_count = _count_paths(grid,r,c+1,memo)
  memo[pos] = down_count + right_count
  return down_count + right_count

用户疑问 #

该函数运行有效，但无法理解其如何统计所有可行路径：当基例返回1时，若前两次递归返回down_count + right_count = 2，为何后续递归会将该值加入计算？原以为这个2会丢失，应该仅再次计算down_count + right_count。

逻辑拆解 #

核心规则是：当前位置到终点的可行路径数 = 下方位置到终点的路径数 + 右方位置到终点的路径数，一步步看具体过程：

1. 基例的意义

   • 走到终点时返回1：代表这条分支是1条有效路径。
   • 出界或碰到墙返回0：代表这条分支是无效路径，贡献0条。

2. 递归的累加逻辑
   举个简单场景：假设终点前有两个位置，一个在终点正上方（只能向下到终点），一个在终点正左方（只能向右到终点）。

   • 上方位置的递归：down_count是终点返回的1，right_count是0（比如右方出界），所以这个位置的路径数是1+0=1，这个值会返回给调用它的上一层。
   • 左方位置同理，路径数是0+1=1，也返回给上一层。
   • 如果有个位置的下方是刚才的上方位置，右方是刚才的左方位置，那它的路径数就是1+1=2——这个2不会丢失，它会作为这个位置的路径数返回给更上层的调用，成为上层计算的一部分。

   本质上，每个递归调用的返回值，都是当前位置到终点的总路径数，这个值会被传递给父调用，父调用把两个方向的数值相加，得到自己位置的总路径数，再继续向上传递，直到回到起点(0,0)，最终得到的就是全局总路径数。

3. 备忘录（memo）的作用
   同一个位置可能被多个不同的递归分支访问到，比如某个中间位置，既可以从上方走下来，也可以从左方走过来。备忘录会把已经计算好的位置路径数存起来，下次再访问时直接返回结果，避免重复计算，提升效率。

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