在网格中查找最佳长路径

Question

给定是一个N*N网格.现在我们需要找到一个最大长度的好路径,其中好的路径定义如下:

1. 好路径始终从标记为0的单元开始
2. 我们只允许向左,向右,向上或向下移动
3. 如果ith cell的值为A,则路径中下一个单元格的值必须为A + 1.

现在给出这几个条件,我需要找出可以进行的最大路径的长度.另外,我需要计算最大长度的路径.

示例:设N = 3,我们有3*3矩阵如下:

0 3 2               
3 0 1               
2 1 0            

那么此处的最大良好路径长度为3,并且这种良好路径的计数为4.

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

Answer 1

这个问题是最长路径问题的变体，但是您的限制使这个问题变得更容易，因为该图实际上是有向无环图（DAG），因此该问题可以有效解决。

定义有向图G=(V,E)如下：

• V = { all cells in the matrix}（健全性检查：|V| = N^2）
• E = { (u,v) | u is adjacent to v AND value(u) + 1 = value(v) }

请注意，上述定义生成的图是 DAG，因为您不能有任何循环，因为它将导致具有一些边，e= (u,v)例如value(u) > value(v)。

现在，您只需找到DAG 中从任意起点开始的最长路径即可。这是通过对图进行拓扑排序，然后使用动态规划来完成的：

init:
for every source in the DAG:
D(v) = 0            if value(v) = 0
       -infinity    otherwise
step:
for each node v from first to last (according to topological sort)
   D(v) = max{D(u) + 1 | for each edge (u,v) }

完成后，找到v具有最大值的节点D(v)，这就是最长的“好路径”的长度。
找到路径本身是通过重新滚动上面的内容来完成的，从最大 D(v) 回溯你的步骤，直到回到值为 0 的初始节点。

这种方法的复杂度是O(V+E) = O(n^2)

由于您正在寻找最长路径的数量，因此您可以稍微修改此解决方案以计算到达每个节点的路径数量，如下所示：

Topological sort the nodes, let the sorted array be arr (1)
For each node v from start to end of arr:
   if value(v) = 0:
        set D(v) = 1 
   else
        sum = 0
        for each u such that (u,v) is an edge: (2)
            sum = sum + D(u) 
        D(v) = sum

上面的代码将为您找到每个节点到达该节点的v“好路径”的数量。现在您所要做的就是找到具有总和节点的D(v)最大值，例如和，并对到达任意节点的路径数求和：xvvalue(v) = xD(v) > 0value(v)

max = 0
numPaths = 0
for each node v:
    if value(v) == max:
         numPaths = numPaths + D(v)
    else if value(v) > max AND D(v) > 0:
         numPaths = D(v)
         max = value(v)
return numPaths

注意： (1) - “常规”排序在这里起作用，但需要 O(n^2logn) 时间，而拓扑排序需要 O(n^2) 时间
(2) 提醒，(u,v) 是一个边缘如果： (1)u和v相邻 (2) value(u) + 1 = value(v)