leetcode 【 Unique Paths 】python 实现

题目：

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]

思路：

动态规划经典题目，用迭代的方法解决。

1. 先处理none case和special case

2. 2D-matrix的第一行和第一列上的元素只能从上面的元素或左边的元素达到，因此可以直接获得其值

3. 遍历其余的位置：每一个position只能由其左边或者上边的元素达到，这样可得迭代公式 dp[row][col]=dp[row-1][col]+dp[row][col-1]

4. 遍历完成后 dp矩阵存放了从其实位置到当前位置的所有可能走法，因此返回dp[m-1][n-1]就是需要的值