此问题是“
最长路径问题”的变体，但是您的限制使此问题更加容易，因为该图实际上是有向无环图（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)。所有你现在要做的，就是找到的最大价值x在于拥有和节点v，使得value(v) = x和D(v) > 0，总结路径达成任何节点编号为value(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）值（u）+ 1 =值（v）