題目：

A robot is located at the top-left corner of a?m?x?n?grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note:?m?and?n?will be at most 100.

?

代碼：oj測試通過?Runtime:?44 ms

1 class Solution: 2 # @return an integer 3 def uniquePaths(self, m, n): 4 # none case 5 if m < 1 or n < 1: 6 return 0 7 # special case 8 if m==1 or n==1 : 9 return 1 10 11 # dp 12 dp = [[0 for col in range(n)] for row in range(m)] 13 # the elements in frist row have only one avaialbe pre-node 14 for i in range(n): 15 dp[0][i]=1 16 # the elements in first column have only one avaialble pre-node 17 for i in range(m): 18 dp[i][0]=1 19 # iterator other elements in the 2D-matrix 20 for row in range(1,m): 21 for col in range(1,n): 22 dp[row][col]=dp[row-1][col]+dp[row][col-1] 23 24 return dp[m-1][n-1]

?

思路：

動(dòng)態(tài)規(guī)劃經(jīng)典題目，用迭代的方法解決。

1. 先處理none case和special case

2. 2D-matrix的第一行和第一列上的元素 只能從上面的元素或左邊的元素達(dá)到，因此可以直接獲得其值

3. 遍歷其余的位置：每一個(gè)position只能由其左邊或者上邊的元素達(dá)到，這樣可得迭代公式?dp[row][col]=dp[row-1][col]+dp[row][col-1]

4. 遍歷完成后 dp矩陣存放了從其實(shí)位置到當(dāng)前位置的所有可能走法，因此返回dp[m-1][n-1]就是需要的值

?

轉(zhuǎn)載于:https://www.cnblogs.com/xbf9xbf/p/4250359.html

總結(jié)

以上是生活随笔為你收集整理的leetcode 【 Unique Paths 】python 实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。