Medium, Dynamic Programming
Question
一个机器人在mxn的矩阵的左上角，想要移动到右下角，它只能向右或者向下移动，请问有多少不同路径
上图是 3 x 7 的矩阵.
Note: m and n will be at most 100.
Answer
典型的DP问题。（r,c)格点有两个选择, (r, c) --> (r+1, c)或者(r, c) --> (r, c+1)，UP(r, c) == UP(r+1, c) + UP(r, c+1).
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
mat = [[-1 for j in range(n+1)] for i in range(m+1)]
return self.backtrack(0,0,m,n,mat)
def backtrack(self, r,c,m,n,mat):
if r == m-1 and c == n-1:
return 1
if r>=m or c >= n:
return 0
if mat[r+1][c] == -1:
mat[r+1][c] = self.backtrack(r+1,c,m,n,mat)
if mat[r][c+1] == -1:
mat[r][c+1] = self.backtrack(r,c+1,m,n,mat)
return mat[r+1][c] + mat[r][c+1]
以上是top-down的DP解法。下面是更加直接的Bottom-Up的方法
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
mat = [[0 for j in range(n+1)] for i in range(m+1)]
mat[m-1][n] = 1
for i in range(m-1, -1, -1):
for j in range(n-1,-1,-1):
mat[i][j] = mat[i+1][j]+mat[i][j+1]
return mat[0][0]
当然，这道题其实也是一个组合问题，就是从m+n-2个步骤中选择m-1步向下，或者选择n-1步向右
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
import math
return math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1)
