Table of Contents
1 Problem
Starting in the top left corner of a 2*2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20*20 grid?
2 Solution
设左上角坐标为(0,0),右下角坐标为(n,n),则有
递归式:
path(i, j) = path(i-1, j) + path(i, j-1)
因为只能向右或向下运动，故处于某点(i,j)时的路径数为与此点相邻的(i-1,j)和(i,j-1)路径数之和.
递归终止条件为当点位于最右(最下)时，其路径数是唯一的,只能一直向下（向右),即path(n,i) = 1, path(i,n) = 1
从数学的角度看,只需要用到高中的排列组合.从源到目的地共需要移动n + n步,求其路径数即求哪些步骤向右哪些步骤向下，即：
path = \(C_{2n}^{n}\)
当然对于a*b的格子路径数也是同样的做法
3 Answer
137846528820
Source:C++