机器人位于如下图 m x n网格的左上角，通过移动到达网格的右下角。但它的每次移动只能是向下或者向右移动一格，请问从起点到终点共有多少种走法？
?问题来自于leetcode第62号题目，经过深入地摸索发现，在这个机器人的魔性步伐里居然隐藏着一个“杨辉三角形”。先来看看，如何解决这个第62题：
?方法一： 很明显，机器人到达地图上第一行或者第一列的任一点，都只有?1种走法。到第2行居然是 1,2,3,4,....? 到第3行发现第二格开始就是前一格和上一格的和。于是用数学归纳法推断出一个结论：任意点的走法数是 map[i][j] = map[i-1][j] + map[i][j-1] ，i>0,j>0；map[0][j]=map[i][0]=1。
?代码如下：
>>> def paths(m,n):
map = [[1 for _ in range(n)] for _ in range(m)]
for i in range(1,m):
for j in range(1,n):
map[i][j] = map[i-1][j] + map[i][j-1]
return map[m-1][n-1]
>>> m,n = 2,3
>>> paths(m,n)
3
>>> m,n = 3,3
>>> paths(m,n)
6
>>> m,n = 3,7
>>> paths(m,n)
28
>>> 方法二： 还是上面的思路，把地图扩展到正方形可以看出对角线串连的数字正是一个标准的杨辉三角形。如果杨辉三角形的每一行用一个列表A表示，第m行第n列的走法数值出现在A[m+n-1]的第m个(或第n个，两者的值相等)位置上。
代码如下：?
>>> def Yh(m,n):
i = m+n-1
t = L = [1]
while(i>1):
i -= 1
t = L+[t[n]+t[n+1] for n in range(len(t)-1)]+L
return t[m-1]
>>> Yh(3,2)
3
>>> Yh(7,3)
28
>>> Yh(7,7)
924
>>> 方法三： 问题的本质：对m行n列的网格来说，就是n-1个Right和m-1个Down放到一起的排列问题，结果 result = (m-1+n-1)! / [(m-1)! * (n-1)!]
>>> def perm(n):
s=1
while n:
s*=n
n-=1
return s
>>> def result(m,n):
return perm(m+n-2)//perm(m-1)//perm(n-1)
>>> m,n = 3,2
>>> result(m,n)
3
>>> m,n = 7,3
>>> result(m,n)
28
>>> 加强版 第63题
当地图上的某一点出现障碍物，路径数有什么变化？？
方法一：参照前一题方法一的思路，只是到有障碍的地方走法数为零；先创建一个地图生成器：表示m行n列的网格，障碍位置x行y列，设置时0和1与题目中的示例刚好相反，有障碍的位置为0，其余都为1，如下：
>>> Map = lambda m,n,x=2,y=2:[[0 if (i,j)==(x-1,y-1) else 1 for j in range(n)] for i in range(m)]
>>> Map(3,3)
[[1, 1, 1], [1, 0, 1], [1, 1, 1]]
>>> Map(3,7,2,3)
[[1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1]]
>>> ?然后在此地图的第二行第二列开始照前一题的样子“做加法”，但遇到0要跳过：
代码如下：?
>>> def Paths(m,n,x=2,y=2):
map = [[0 if (i,j)==(x-1,y-1) else 1 for j in range(n)] for i in range(m)]
for i in range(1,m):
for j in range(1,n):
if map[i][j]!=0:
map[i][j]=map[i-1][j]+map[i][j-1]
return map[m-1][n-1]
>>> Paths(3,3)
2
>>> Paths(3,7,2,3)
13?方法二：解题思路是用无障碍时的走法总数减去经过障碍那一点的走法数；后者等于起点到障碍点的走法数与障碍点到终点的走法数的乘积。调用上一题的paths(m,n)，引入障碍坐标x,y表示x行y列有障碍。所求结果即等于：??paths(m,n) - paths(x,y)*paths(m-x+1,n-y+1)
代码如下：?
>>> def paths(m,n):
r = [[1 for _ in range(m)] for _ in range(n)]
for i in range(1,n):
for j in range(1,m):
r[i][j] = r[i-1][j]+r[i][j-1]
return r[n-1][m-1]
>>> m,n=3,3; x,y=2,2
>>> paths(m,n) - paths(x,y)*paths(m-x+1,n-y+1)
2
>>> m,n=3,7; x,y=2,3
>>> paths(m,n) - paths(x,y)*paths(m-x+1,n-y+1)
13
>>> ?当问题扩展到有多个障碍物时，凡是有障碍的格子就都置成0估计也能成立(没实测)！
————===== The End =====————