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.
Tags：Array，Dynamic Programming
Similar Problems: Unique PathII，Minimum Path Sum，Dungeon Game
法1：动态规划，分析：求解path的种类数量（种类数动规/棋盘类动规） 设dp[i][j]表示从左上角到达grid[i][j]时的种类数，则dp[i][j] = dp[i-1][j]+dp[i][j-1] 空间复杂度O(m*n)，时间复杂度O(m*n)
代码实现：
class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ #1.先做输入处理 if m==0 or n==0: return 0 #2.初始化，同时注意dp[0][0]的值 dp = [ [1]*n for i in range(m) ] #3.dp for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j]+dp[i][j-1] return dp[-1][-1] 法2：数学方法--组合问题，分析：从示例可以看出，必然要走8步，且其中有2步是向下走，剩余6步向右走；即对于m*n的网格来说，m-1次向下走，n-1次向右走，则一共要走m+n-2步，走法是C(m+n-2, m-1) C(m, n)=m*(m-1)* ... *(m-n+2)*(m-n+1) / n! = (m-n+i)/i, i从1-->n 空间复杂度O(1)，时间复杂度O(n)代码实现：
class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ #1.先做输入处理 if m==0 or n==0: return 0 def cmn(m, n):#求解组合数C(m, n)，即在m个中选出n个的选择方法数 if n==0: return 1 res = 1 for i in range(1, n+1): res *= m-n+i res /= i return res return cmn(m+n-2, m-1)