（最短路线）某城市的街道是一个很规整的矩形网格（见下图）,有7条南北向的纵街,5条东西向的横街.现要从西南角的A走到东北角的B,最短的走法共有多少种?即（4行6列的矩形

Question

（最短路线）某城市 的街道是一个很规整的矩形网格（见下图）,有7条南北向的纵街,5条东
西向的横街.现要从西南角的A走到东北角的B,最短的走法共有多少种?_________________
即（4行6列的矩形）
应该有公式的,网上没找到,

Answer 1

解法1：利用递推公式.设m条纵街与n条横街的最短走法为A(m,n),易知A(m,1)=A(1,n)=1,当m>1且n>1时,由于第1步有向上、向右两种走法,因此有A(m,n)=A(m-1,n)+A(m,n-1),因此可利用下面的表格计算A(5,7)：M123456711111111212345673136101521284141020355684515153570126210在上表中,除第1行与第1列外,每个格中的数都等于该格上方的数与该格左边的数之和.注意在题目的表格中,A点的位置是（5,7）,B点的位置是（1,1）.解法2：利用组合公式.对于m条纵街与n条横街,任何一条可行的路径都包括n-1段纵街（由n条横街分割而成）和m-1段横街（由m条纵街分割而成）构成,我们可以把一条可行的路径理解为一条线段,上面共有(n-1)+(m-1)个连续的等距的小格,我们从中选n-1个小格走纵街,其余的m-1个小格走横街,于是,不同的选择方法共有210.