algorithm - 给定一个 NxN 矩阵，我怎样才能找到到某个位置 (i,i) 的所有可能路径？

Question

给定一个NxN矩阵，我怎么能找到一个 location 的所有可能路径(i,i)。导航将只downwards和朝向right。起点是(0,0)。

PS不是作业。

score 2 · Accepted Answer

?

对于一个位置 (i, i)，即对角线上的一个位置，正好有 comb(i, 2 * i) 路径（从一组 2 * i 个元素中选择 i 个元素的方法的数量），每个路径由 i 个动作组成向右和我向下运动。枚举它们是微不足道的。

score 2 · Accepted Answer

最简单的（对我来说）是递归地做：

1) 停止条件将到达 (i,i)

2）您将在每个递归级别尝试两个下一步动作：

假设您当前的位置是 (x,y)：如果您当前的 "y" 加 1 比 (i,i) 中的 "i" 大，则您不能正确。如果您当前的“x”加 1 大于 (i,i) 中的“i”，则您不能下降。

您只需要记住某个变量中的路径或将其向下传递并在停止条件发生时打印它。

因此，假设您从 (0,0) 开始，您会记住这一点，然后检查您是否可以向右或向下，如果两者都是，那么您递归地为 (0,1) 和 (1,0) 调用相同的方法。

score 2 · Accepted Answer

尽管您可以使用 DP 来解决这个问题，但这只是简单的数学运算：

你必须2i迈出一步，从那里i必须是向右的步骤。总组合为C(2i,i)。请参阅：计算二项式系数。

另一个类似的问题是你不能穿过对角线，称为单调路径，有趣的加泰罗尼亚数列就是解决方案。

score 1 · Accepted Answer

解决方案 1 - 使用动态编程：

将解决方案自下而上加起来，直到您想要的 (i,j) 索引：

ans(i,i) = ans(i-1,j) + ans(i,j-1)

并将相同的用于位置（i，i）。

解决方案 2 - 使用简单的排列和组合

ans = (2i)!/i!i!

（因为您必须选择从 (0,0) 开始向右的 i 步和向下的 ji 步，总共是 2i 步）。

score 1 · Accepted Answer

从 45 度角看问题。您会看到您正在尝试计算三角形数组上顶点的路径数。解由帕斯卡三角形给出。

2i choose i

score 1 · Accepted Answer

这取决于您何时从 (0,0) 或矩阵中的随机位置开始。

如果是 (0,0) ；使用深度优先直到一个分支结束，然后是其他分支。使用广度优先一步遍历所有相邻节点。仅检查向下和右侧节点。

如果它位于矩阵中的随机位置，则需要跟踪所有 4 个相邻节点。

6 回答 6