在具有多个检查点的网格中计算路径

Question

给定网格尺寸N X N。其左下角的点是(0,0)，右上角的元素是(N-1,N-1)。

我们可以向上或向右的方向遍历网格。我们必须找到从左下角到右上角的遍数的方法。 有一些检查点我们必须在每个路径访问。至少有一个有效的路径。

例：让N=5，我们有1个检查站(2,2)那么这里的答案是36。

注意：我只需要计算有效路径，不必担心找到它们。

什么可以有效的方法来计算它们？

Answer 1

你必须知道两件事情：

1. Rule of product：这意味着一些从开始到结束的方式是从开始的方式相同数量的中间点*从中间点的方式来结束编号。

2. C（R，R + U）（R是您正确的动作数量和U是不是就意味着，如果你想要去的(a,b)到(c,d)然后R = c-a和U = d-b最多的移动次数，并C(R,R+U) = (R+U)!/R!U!）是网格中从左下到右上有多少种方式的答案。

例从我的第二个规则的例子有：

从0许多来自(0,0)移动到(2,2)，因为后两个右移动你达到2后从0两个上移动到达2 so R=2 and U=2 so C(2,2+2) = C(2,4) = 4!/2!2! = 6。而做同样的R和U许多来自(2,2)移动到(4,4)是C(2,2+2) = C(2,4) = 4!/2!2! = 6

，并从我们的一切可能的行动数的第一条规则：6 * 6 = 36

Answer 2

使用动态规划：

dp[k, i, j] = number of paths from checkpoint k to (i, j) 

dp[k, i, j] = dp[k, i - 1, j] +  top 
       dp[k, i, j - 1]   right 

答案是检查点之间dp值的乘积。

注意：您可以通过实现矩阵中的实际位置并不重要，只是位置和检查点位置之间的相对距离来避免第一维。

Answer 3

这一特定问题的关键是找到数的子点之间的路径（根据各自的位置进行排序后），然后乘以所有路径数。

这里的解决办法是：从源

1排序点至目的地。

示例： 如果开始点是[0,0]结束点是[10,10]和中间点是[5,6]，[2,4] & [8,8]，则排序点（包括源和目的地）将是[0,0]，[2,4]，[5,6]，[8,8]，[10,10]在一个11×11矩阵

2.查找从源到下一个子目的地的路径数量（最好使用DP）。 （在排序点的顺序）

在上面的例子中，需要计算将是以下各点之间的路径的数目：

[0,0]到[2,4]

[2,4]到[5,6]

[5,6]到[8,8]

[8,8]到[10,10]

3。找到th的所有上述4条个子路径

E产品就是这样

下面是用于查找的路径数的solution（见DP的方法）从源和目的地。你不需要传递矩阵作为参数，因为这是不需要的。只需要[x，y] [X，Y]形式的源点和目标点。除了链接中的代码之外，其他部分（排序点和乘法）必须按照上面的解释进行。