algorithm - 如何在 m×n 矩阵中找到从 (1, 1) 到 (m, n) 的所有可能路径？

Question

假设我们有一个起始索引为 (1, 1) 的 m×n 矩阵。我们必须通过向右或向下移动到相邻元素来到达位置 (m, n)。我们如何探索所有可能的路径？

标签： algorithmmatrix

Answer 1

将帕斯卡三角形转 1/8 圈：

1  1  1  1  1 ...
1  2  3  4  5 ...
1  3  6 10 15 ...
1  4 10 20 35 ...

该矩阵的元素 [M, N] 是您想要的答案。

这个数组的构造与帕斯卡三角形的构造是同构的：

从 (1, 1) 开始；只有一种方法可以到达那个地方。下一步是到 (2, 1) 或 (1, 2) - 只有一种方法可以到达那个位置。在下一步中，现在有两种到达 (2, 2) 的方式：它可以从前面的任何一个点到达，所以方式的数量是这两个元素的总和。这就是帕斯卡三角形的临界同构。

---

更直接地说，只需对三角形的任何元素使用公式：

(a+b)! / a!b!

其中 a = M-1，b = N-1

这是您需要的数量right和down移动，使用组合公式对其所有排列。