想法是从 N*N 矩阵的左上角移动到右下角,其中唯一允许的移动是向下或向右。不允许回溯。这使用动态规划很简单,如下所示 geeks for geeks关联。我试图了解如何使用简单的排列和组合来实现相同的目的。我遇到了以下 BetterExplained关联。他们正在解决的问题肯定不匹配。有没有办法使用排列组合找到解决方案?可以帮助我更好地理解解决方案的指针?
编辑 1:
下面是一个3X3矩阵的例子,当我们进行动态规划时,它显示了从左最上点到最右下点的6种方法,这只有在使用公式时才可行2(N-1)!/(N-1)!(N-1)!
。但是我在下面列出了20种从起点到达终点的方法,即2N!/N!*N!
或者我理解错误是可行的问题,我们已经在左最上面的单元格并遍历到右最下面的单元格,在这种情况下答案将是 6
最佳答案
在 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)
移动到执行。
关于algorithm - 使用排列组合遍历 N*N 矩阵的方法数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55492275/