algorithm - DAG 与查找网格中 2 个节点之间的路径之间的关系

Question

漫游者算法指南讨论了以下要点:

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 本身，我读到如果我们在网格中仅朝两个方向移动，那么我们可以假设它是一个 DAG。这个问题听起来可能很幼稚，但我是初学者，我们将不胜感激任何帮助。

Answer 1

网格中的每个点都是一个顶点。你有 m * n 个顶点。从每个顶点到表示其左侧点的顶点以及从每个顶点到表示其顶部点的顶点都有一条边。

DAG 这样表示网格。