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]
當(dāng)然，這道題其實也是一個組合問題铣猩，就是從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)
