Hitchhiker 的算法指南讨论了以下几点:
1.6 Counting or Optimizing Good Paths
In an n × m grid, we want to go from the left bottom corner to the upper right corner. Each
time we can only take a step to the right, or a step up. The number of ways we can do this
is exactly (n+m)!/(n! * m!). But what if we forbid some points on the grid? For example, if we
forbid all the points above the line y = x. Some of the problems has answer in closed formula.
But all of them can be solved quickly by dynamic programming.
Problem 1.6 Given a directed acyclic graph, how many paths are there from u to v? What is the longest one if there are weights on the edges?
我的问题是这两个问题有什么关系?这里的网格和 DAG 之间有什么关系。在stackoverflow本身上,我读到如果我们只在网格中的两个方向上移动,那么我们可以假设它是一个有向无环图。这个问题可能听起来很幼稚,但我是一个初学者,任何帮助将不胜感激。