# 62. Unique Paths 不同路径

## # 题目描述：

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?

## # 解题方法

### # 方法一：组合公式

``````class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
total = m + n - 2
v = n - 1
def permutation(m, n):
son = 1
for i in range(m, m - n, -1):
son *= i
mom = 1
for i in range(n, 0, -1):
mom *= i
return son / mom
return permutation(total, min(v, total -v))
``````

### # 方法二：记忆化搜索

``````class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
memo = [[0] * n for _ in range(m)]
return self.dfs(m - 1, n - 1, memo)

def dfs(self, m, n, memo):
if m == 0 or n == 0:
return 1
if memo[m][n]:
return memo[m][n]
up = self.dfs(m - 1, n, memo)
left = self.dfs(m, n - 1, memo)
memo[m][n] = up + left
return memo[m][n]
``````

### # 方法三：动态规划

``````class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for i in range(n):
dp[0][i] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
return dp[m - 1][n - 1]
``````

``````class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[1] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
continue
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
return dp[m - 1][n - 1]
``````

``````class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
dp[1][1] = 1;
for (int i = 1; i < m + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
if (i == 1 && j == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};
``````

## # 日期

2018 年 2 月 19 日 2018 年 10 月 18 日 2018 年 12 月 29 日 —— 2018年剩余电量不足1%