动态规划实现带障碍物迷宫路径计数时触发KeyError(0,8)问题排查

• 第一行填充逻辑的循环范围存在根本性错误：原代码中障碍物分支的for k in range(j,)等价于for k in range(j)——Python中仅传一个参数给range时，该参数代表循环终止值，循环会从0遍历到j-1，完全没有覆盖当前障碍物位置及其右侧所有单元格的赋值。比如测试迷宫第一行第8列是障碍物（坐标(0,8)），进入分支后循环仅会给0-7列赋值0，(0,8)、(0,9)两个坐标的键从来没有被写入字典，后续DP计算到第二行第8列时，需要取上方相邻的(0,8)的路径值，直接触发KeyError: (0,8)。
• 第一列填充逻辑存在规则漏洞：原代码遇到障碍物时仅给当前障碍物位置赋值0，没有将障碍物下方所有单元格的路径数设为0，后续单元格只要取值为1就会错误赋值为1，不符合障碍物阻断通行的规则。
• 字典存储的天然缺陷：因为没有对所有可能访问的坐标做提前赋值，只要DP计算路径上有未写入的键，就会触发键不存在的报错。

字典实现版本（兼容原有代码逻辑） #

用阻断标记替代嵌套循环，保证所有第一行、第一列的坐标都被写入字典：

def num_of_paths(maze):
    table = {}
    n = len(maze)
    if n == 0:
        return 0
    m = len(maze[0])
    # 填充第一行
    blocked = False
    for j in range(m):
        if blocked:
            table[(0, j)] = 0
            continue
        if maze[0][j] == 0:
            blocked = True
        table[(0, j)] = 0 if blocked else 1
    # 填充第一列
    blocked = False
    for i in range(n):
        if blocked:
            table[(i, 0)] = 0
            continue
        if maze[i][0] == 0:
            blocked = True
        table[(i, 0)] = 0 if blocked else 1
    # 主DP逻辑
    for i in range(1, n):
        for j in range(1, m):
            if maze[i][j] == 0:
                table[(i, j)] = 0
            else:
                table[(i, j)] = table[(i-1, j)] + table[(i, j-1)]
    return table[(n-1, m-1)]

更高效的二维列表实现 #

用二维列表替代字典存储DP值，初始化时所有位置默认赋值为0，从根源上避免键缺失问题，同时降低哈希查找的开销：

def num_of_paths(maze):
    n = len(maze)
    if n == 0:
        return 0
    m = len(maze[0])
    # 初始化DP表，所有位置默认0，天然避免键不存在的问题
    dp = [[0]*m for _ in range(n)]
    # 初始化起点
    if maze[0][0] == 1:
        dp[0][0] = 1
    # 填充第一行：可通行位置的路径数完全等于左侧相邻格的路径数
    for j in range(1, m):
        if maze[0][j] == 1:
            dp[0][j] = dp[0][j-1]
    # 填充第一列：可通行位置的路径数完全等于上方相邻格的路径数
    for i in range(1, n):
        if maze[i][0] == 1:
            dp[i][0] = dp[i-1][0]
    # 填充内部格子
    for i in range(1, n):
        for j in range(1, m):
            if maze[i][j] == 1:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n-1][m-1]

• 上述实现默认移动方向仅为向下、向右，如果迷宫允许其他方向移动，需要调整状态转移逻辑。
• 计算时需要优先判断起点位置是否为障碍物，如果起点不可通行直接返回0即可，避免无意义的计算。

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