原題
有一個(gè)機(jī)器人的位于一個(gè)M×N個(gè)網(wǎng)格左上角（下圖中標(biāo)記為'Start'）。
機(jī)器人每一時(shí)刻只能向下或者向右移動(dòng)一步饰剥。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（下圖中標(biāo)記為'Finish'）鬼贱。
問有多少條不同的路徑撇眯？
| 1, 1 | 1, 2 | 1, 3 | 1, 4 |
|---|---|---|---|
| 2, 1 | |||
| 3, 1 | |||
| 4, 1 | 4, 4 |
以上4 x 4的網(wǎng)格中，有多少條不同的路徑玻熙？
解題思路
- 動(dòng)態(tài)規(guī)劃就是解決了重復(fù)計(jì)算串远，具體實(shí)現(xiàn)方式有：
- 記憶化搜索
- 循環(huán)求解(本題采用此方法)
- 典型DP問題 - 矩陣型動(dòng)態(tài)規(guī)劃(Matrix DP)
-
cache[x][y]表示從起點(diǎn)到x,y的路徑數(shù)宏多，等于cache[x][y - 1]與cache[x - 1][y]的路徑數(shù)之和
完整代碼
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m < 1 or n < 1:
return 0
cache = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
cache[i][0] = 1
for j in range(m):
cache[0][j] = 1
for i in range(1, n):
for j in range(1, m):
cache[i][j] = cache[i - 1][j] + cache[i][j - 1]
return cache[n - 1][m - 1]
