題目:
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）斋荞。
機器人每次只能向下或者向右移動一步耗啦。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）汇鞭。
問總共有多少條不同的路徑耘沼？
說明：m 和 n 的值均不超過 100韧衣。
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始盅藻，總共有 3 條路徑可以到達右下角购桑。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
鏈接：https://leetcode-cn.com/problems/unique-paths
思路：
1、從m x n 網格的左上角走到右下角的方法數等于 (m-1) x n 網格 的方法數 和 m x (n-1) 網格的方法數之和
Python代碼：
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0]*n]*m # 創(chuàng)建一個m*n的矩陣
dp[0][0] = 0
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
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]
C++代碼：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0] = 0;
for (int i=0; i<m; i++){
dp[i][0] = 1;
}
for (int j=0; j<n; j++){
dp[0][j] = 1;
}
for (int i=1; i<m; i++){
for (int j=1; j<n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};