描述

62. 不同路徑
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。

問總共有多少條不同的路徑？

示例 1：

輸入：m = 3, n = 7
輸出：28
示例 2：

輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達右下角。

向右 -> 向下 -> 向下

向下 -> 向下 -> 向右

向下 -> 向右 -> 向下
示例 3：

輸入：m = 7, n = 3
輸出：28
示例 4：

輸入：m = 3, n = 3
輸出：6

提示：

1 <= m, n <= 100
題目數據保證答案小于等于 2 * 109

思路一：動態規劃

class Solution { public:int uniquePaths(int m, int n) {//1:確定dp[i][j]:i,j代表的是位置點,表示從(0,0)出發到(i,j)有dp[i][j]條不同數據vector<vector<int>> dp(m,vector<int>(n,0));//2:確定初始條件for(int i=0;i<m;i++) dp[i][0] = 1;for(int j=0;j<n;j++) dp[0][j] = 1;//3:確定遍歷順序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];} };

總結

以上是生活随笔為你收集整理的LeetCode-动态规划基础题-62. 不同路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。