一:題目

二:上碼

class Solution { public:/**思路:1.分析題意:2.動態規劃五步走:1>:確定dp數組和其下標的含義dp[i][j]為到達二維數組下標為i，j的路徑條數,i和j為下標2>:確定dp數組的遞推公式那么dp[i][j]是如何求解出來的呢?只能是兩個方向左邊:dp[i-1][j]上邊:dp[i][j-1]那么dp[i-1][j]代表的是從坐標(0,0)點開始到dp[i-1][j]的路徑條數dp[i][j-1]同理3>:確定dp數組的初始化那么在二位數組范圍內最上邊一行和最左邊一列都是1，因為到這個路徑均是1所以:for(int i = 0; i < n; i++) {dp[0][i] = 1;}for(int j = 0; j < m; j++) {dp[j][0] = 1;}4>:確定dp數組的遍歷順序從左向右的遍歷。5>:舉例驗證dp數組m = 3,n = 7;1 1 1 1 1 1 11 2 3 4 5 6 71 3 6 10 15 21 28 */int uniquePaths(int m, int n) {int dp[m][n];for(int j = 0; j < n; j++) {//列在變dp[0][j] = 1;}for(int i = 0; i < m; i++) {//行在變dp[i][0] = 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];} };

總結

以上是生活随笔為你收集整理的leetcode62. 不同路径的全部內容，希望文章能夠幫你解決所遇到的問題。

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