##題目描述 一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）， 機器人每次只能向下或者向右移動一步，機器人試圖達到網格的右下角（在下圖中標記為“Finish”）， 
問總共有多少條不同的路徑？
說明：m 和 n 的值均不超過 100，
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達右下角，
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
思路
dp[i][j] = dp[i-1][j] + dp[i][j-1];
時間復雜度O(mn)，空間復雜度O(mn)，
代碼
動態規劃（楊輝三角）
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
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];
}
}
筆記
m,n不大時可以直接使用排列組合公式求解，
鏈接：https://leetcode-cn.com/problems/unique-paths
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90053.html
標籤：其他
上一篇：陣列
下一篇：反碼轉換為補碼