dp問題描述

62.不同路徑

確定本題的狀態表示

dp[i,j]表示的是從左上角走到這個位置的路徑條數

確定本題的狀態轉移方程

根據已知條件：dp[0,0]=1，dp[0,1]=1，dp[1,0]=1
本題的狀態轉移方程是：
dp[i,j]=dp[i,j-1]+dp[i-1,j]

填表求值

根據初始條件和狀態轉移方程，確定填表順序，進而逐步填滿dp表，最終返回題目要的結果

代碼實現

這個題貌似我做過，二維dp問題的入坑題目，不多解釋，直接上代碼

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