62.不同路徑

動規(guī)五部曲：

確定dp數(shù)組（dp table）以及下標的含義

dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

確定遞推公式

想要求dp[i][j]，只能有兩個方向來推導出來，即dp[i - 1][j] 和 dp[i][j - 1]

dp[i - 1][j] 表示從(0, 0)的位置到(i - 1, j)有幾條路徑，dp[i][j - 1]同理

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

dp數(shù)組的初始化

首先dp[i][0]一定都是1，因為從(0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理。

確定遍歷順序

這里要看一下遞推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是從其上方和左方推導而來，那么從左到右一層一層遍歷就可以了

舉例推導dp數(shù)組

intuniquePaths(intm,intn){vector<vector<int>>dp(m,vector<int>(n,0));for(inti=0;i<m;i++)dp[i][0]=1;for(intj=0;j<n;j++)dp[0][j]=1;for(inti=1;i<m;i++){for(intj=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}returndp[m-1][n-1];}

63.?不同路徑?II?

動規(guī)五部曲

確定dp數(shù)組（dp table）以及下標的含義

dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑

確定遞推公式

遞推公式和62.不同路徑一樣，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

(i, j)如果就是障礙的話應該就保持初始狀態(tài)（初始狀態(tài)為0）

dp數(shù)組如何初始化

從(0, 0)的位置到(i, 0)的路徑只有一條，所以dp[i][0]一定為1，dp[0][j]也同理

如果(i, 0) 這條邊有了障礙之后，障礙之后（包括障礙）都是走不到的位置了，所以障礙之后的dp[i][0]應該還是初始值0

下標(0, j)的初始化情況同理

vector<vector<int>>dp(m,vector<int>(n,0));for(inti=0;i<m&&obstacleGrid[i][0]==0;i++)dp[i][0]=1;for(intj=0;j<n&&obstacleGrid[0][j]==0;j++)dp[0][j]=1;

確定遍歷順序

從遞歸公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，一定是從左到右一層一層遍歷，這樣保證推導dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值

舉例推導dp數(shù)組

intuniquePathsWithObstacles(vector<vector<int>>&obstacleGrid){intm=obstacleGrid.size();intn=obstacleGrid[0].size();if(obstacleGrid[m-1][n-1]==1||obstacleGrid[0][0]==1)//如果在起點或終點出現(xiàn)了障礙，直接返回0return0;vector<vector<int>>dp(m,vector<int>(n,0));for(inti=0;i<m&&obstacleGrid[i][0]==0;i++)dp[i][0]=1;for(intj=0;j<n&&obstacleGrid[0][j]==0;j++)dp[0][j]=1;for(inti=1;i<m;i++){for(intj=1;j<n;j++){if(obstacleGrid[i][j]==1)continue;dp[i][j]=dp[i-1][j]+dp[i][j-1];}}returndp[m-1][n-1];}