右上、右、右下路径数：滚动列DP与检查点分段

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• rows/cols>0，起点(rows−1,0)和终点(rows−1,cols−1)，不含障碍。
• 检查点是有序必经点，可重复同一点；同列不同点不可同时访问。无序检查点应按列排序后检查冲突。

解题路线

1. 列严格递增，图为DAG。当前列行r的路径数等于前列r−1/r/r+1的计数和，边界缺项为0。
2. 空间只保留前列与新列，不能原地左到右更新，因为会混入本列结果。
3. 任意从S到T并按序经过P的路径唯一分解为相邻检查点段；各段选择独立，数量相乘。同列同点段有1条零步路径，同列异点有0条。

手动走一遍

2行3列，从(1,0)到(1,2)：中间行可0或1，因此总2。要求checkpoint(0,1)后只剩1。检查点列顺序逆转返回0；若同列(0,1),(1,1)要求同时访问，也为0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def count_paths(rows, cols, checkpoints=()):
    if rows <= 0 or cols <= 0:
        raise ValueError("positive dimensions required")
    points = [(rows - 1, 0)] + list(checkpoints) + [(rows - 1, cols - 1)]
    if any(not 0 <= r < rows or not 0 <= c < cols for r,c in points):
        raise ValueError("invalid point")
    total = 1
    for (sr,sc),(tr,tc) in zip(points,points[1:]):
        if tc < sc:
            return 0
        dp = [0] * rows
        dp[sr] = 1
        for _ in range(tc - sc):
            dp = [dp[r] + (dp[r-1] if r else 0) + (dp[r+1] if r+1<rows else 0) for r in range(rows)]
        total *= dp[tr]
    return total

复杂度

O(rows×总前进列数)时间、O(rows+检查点数)空间；合法有序检查点分段宽度总计cols−1。计数可指数大，整数位成本需另计。

易错点与追问

容易失分的边界

• 别把到同列另一行当作垂直可达，移动合同不允许。
• 逐个点独立算从S到它再相乘会重复前缀，应分相邻段。

继续深挖

• 有障碍时各段DP怎样过滤落点？
• 计数模M与返回字典序第K条路径各需要哪些附加状态？