您描述的动态编程方法称为DAG最短路径。它仅适用于有向无环图（即无循环的图）。它的渐近运行时间是O（V
+ E）（其中V和E分别是顶点和边的数量），比Dijkstra的算法快。

我不确定，但是您是否在问如何计算长度等于最短路径的路径数？

当您计算最短路径的长度时，可以通过维护先前信息来做到这一点。当您移动到节点j时，存储所有对（i，j），以使从i到j成为最短路径的一部分。实现此目的的一种方法是添加两个字段D（x，y）.optimalUp和D（x，y）.optimalRight（数据类型为boolean），指示通过输入（x，y）是否获得最佳解向上或向右。例如，如果从（x，y-1）上升会导致最便宜的路径，则将D（x，y）.optimalUp设置为true。

然后，您可以使用动态编程进行第二遍计算最便宜的路径数。添加另一个字段，例如D（x，y）.count（整数），该字段保存以最便宜的方式从A到（x，y）的方式数。有两种到达（x，y）的方式：通过（x-1，y）和（x，y-1）。（x，y-1）的计数仅应通过（x，y-1）到达（x，y）的最便宜路径时才应添加到（x，y）的计数中。（x-1，y）的原理相同。

然后，我们得到复发：

D(x,y).count =
    D(x,y).optimalUp   ? D(x,y-1).count : 0
  + D(x,y).optimalDown ? D(x-1,y).count : 0

（？：是C / C ++ / Java中的条件运算符。）

从图片来看，您的图形似乎是网格。注意仅向上或向右行驶不一定会导致路径最短。在下图中，从A到B的最短路径是8，但是如果只向右上走，您的成绩就不会超过12。

x -1-- x -1-- B
|      |      |
1      9      9
|      |      |
x -1-- x -1-- x
|      |      |
9      9      1
|      |      |
A -1-- x -1-- x

由于这被标记为作业，因此我现在不会提供更多细节。不过，这应该是朝着正确方向发展的步伐（如果我正确理解了您的问题）。不过，请随时提出后续问题。