网格每步恰好下降一：最长路径的值域拓扑DP

题意与假设

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

• 矩形整数网格，四方向移动，每步从v到v−1；路径长度按节点数。
• 空网格返回0。不是允许任意幅度下降，不能跨越非相邻格。

解题路线

1. 每条边严格降值，因此不会有环。先按值升序处理，低值格的最长后缀已计算。
2. dp[r,c]=1+max(dp[neighbor])，只选邻居值恰为当前−1。没有符合邻居时为1。
3. 排序基线容易证明且不依赖递归深度。更优O(RC)方案可用拓扑入度/出度分层，每条网格边只访问常数次；别把排序示例标成O(RC)。

手动走一遍

[[3,2],[4,1]]可以4→3→2→1长度4。[[9,1]]没有差1邻接，答案1，任意严格下降版却为2。

Python 参考实现

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

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

def longest_descent(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("ragged grid")
    best = {}
    for value, r, c in sorted((grid[r][c], r, c) for r in range(rows) for c in range(cols)):
        best[r, c] = 1 + max((best[nr, nc] for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)) if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == value - 1), default=0)
    return max(best.values(), default=0)

复杂度

V=RC，示例O(VlogV)时间、O(V)空间。若值域小可桶排，或用图拓扑改为O(V)。

易错点与追问

容易失分的边界

• 相同值间没有边，不能组成平台路径。
• 只减1仍可能有非常长路径，递归memo需栈深保护。

继续深挖

• 返回具体最长路径，怎样存后继并处理并列？
• 允许上下跳±1后为什么成环，最长简单路径为什么困难？