一彬呻、題目描述
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）俩功。機器人每次只能向下或者向右移動一步。機器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）耗绿。問總共有多少條不同的路徑吓妆？
示例：
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始嗜历，總共有 3 條路徑可以到達(dá)右下角宣渗。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
輸入: m = 7, n = 3
輸出: 28
二抖所、代碼實現(xiàn)
方法一、二維矩陣
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m == 0 or n == 0: return 0
dp = [[0] * n] * m
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
方法二痕囱、一維矩陣
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m == 0 or n == 0: return 0
dp = [0] * n
for i in range(m):
for j in range(n):
if i == 0: dp[j] = 1
elif j == 0: dp[j] = 1
else: dp[j] = dp[j] + dp[j-1]
return dp[-1]
