algorithm - 使用排列组合遍历 N*N 矩阵的方法数

Question

想法是从 N*N 矩阵的左上角移动到右下角，其中唯一允许的移动是向下或向右。不允许回溯。这使用动态规划很简单，如下所示 geeks for geeks关联。我试图了解如何使用简单的排列和组合来实现相同的目的。我遇到了以下 BetterExplained关联。他们正在解决的问题肯定不匹配。有没有办法使用排列组合找到解决方案？可以帮助我更好地理解解决方案的指针？

编辑 1:

下面是一个3X3矩阵的例子，当我们进行动态规划时，它显示了从左最上点到最右下点的6种方法，这只有在使用公式时才可行2(N-1)!/(N-1)!(N-1)!。但是我在下面列出了20种从起点到达终点的方法，即2N!/N!*N! 或者我理解错误是可行的问题，我们已经在左最上面的单元格并遍历到右最下面的单元格，在这种情况下答案将是 6

Answer 1

在 2(n-1) 种 种方法中，有 (n-1) 种方法可以按照您给定的规则遍历 n*n 矩阵。

一个简单的解释:由于唯一允许的移动是向下或向右，路径的长度必须正好是2(n-1).
不仅如此，在这条路径中，会有n-1次向下移动，n-1次向右移动>(这是从左上角到达右下角的唯一可能方法)。
所以 (n-1) among 2(n-1) 来自所有可能的方式来适应 n-1 在 2(n -1) 移动到执行。