给定一个NxN
矩阵,我怎么能找到一个 location 的所有可能路径(i,i)
。导航将只downwards
和朝向right
。起点是(0,0)
。
PS不是作业。
给定一个NxN
矩阵,我怎么能找到一个 location 的所有可能路径(i,i)
。导航将只downwards
和朝向right
。起点是(0,0)
。
PS不是作业。
?
对于一个位置 (i, i),即对角线上的一个位置,正好有 comb(i, 2 * i) 路径(从一组 2 * i 个元素中选择 i 个元素的方法的数量),每个路径由 i 个动作组成向右和我向下运动。枚举它们是微不足道的。
最简单的(对我来说)是递归地做:
1) 停止条件将到达 (i,i)
2)您将在每个递归级别尝试两个下一步动作:
假设您当前的位置是 (x,y):如果您当前的 "y" 加 1 比 (i,i) 中的 "i" 大,则您不能正确。如果您当前的“x”加 1 大于 (i,i) 中的“i”,则您不能下降。
您只需要记住某个变量中的路径或将其向下传递并在停止条件发生时打印它。
因此,假设您从 (0,0) 开始,您会记住这一点,然后检查您是否可以向右或向下,如果两者都是,那么您递归地为 (0,1) 和 (1,0) 调用相同的方法。
解决方案 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 步)。
从 45 度角看问题。您会看到您正在尝试计算三角形数组上顶点的路径数。解由帕斯卡三角形给出。
2i choose i
这取决于您何时从 (0,0) 或矩阵中的随机位置开始。
如果是 (0,0) ;使用深度优先直到一个分支结束,然后是其他分支。使用广度优先一步遍历所有相邻节点。仅检查向下和右侧节点。
如果它位于矩阵中的随机位置,则需要跟踪所有 4 个相邻节点。