从左上到右下遍历二维阵列的方法数

由于每条路径由m-1个水平台阶和n-1个垂直台阶组成,因此每条路径中总共有m+n-2个台阶。要选择特定路径,可以定义垂直或水平台阶。假设您已经定义了所有垂直台阶(即其中的n-1个)。一旦定义了它们,就没有其他步骤(水平步骤)的实际选择-每个水平步骤只有一种可能性(在相邻垂直步骤之间建立连接)。因此,从m+n-2中选择n-1定义了一条有效路径。路径总数将是从m+n-2中选择n-1的可能性数(选择m-1而不是n-1可以获得相同的结果)。

参见以下示例:

假设您选择了垂直步骤(红色步骤)-完成后,每个水平步骤只有一个选项(蓝色步骤)。否则,路径将是非连续的,因此无效。

我认为问题陈述是不完整的,只有在每一步你只能向上或向右时,解析解才有效 如果我们只能向上或向右,那么我们需要 (n - 1) + (m - 1) 步骤,到达中的左上角 (n - 1) 在这些步骤中,我们必须向右走,在其他步骤中,我们必须向上走 问题的答案是 ((n + m - 2) choose (n - 1)) or ((n + m - 2) choose (m - 1))