Num 62 不同路径 && Num 63 不同路径 ||
两道题都是基础动态规划,注意求总可能的题是上一可能节点相加
虽然数据范围只有100*100,但是可能结果爆int的,用long表示
有障碍的就多了一个筛选条件
代码如下
class Solution { public: int uniquePaths(int m, int n) { int dp[105][105]; memset(dp,0,sizeof(dp)); dp[1][1]=1; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(i>=2 && j>=2) dp[i][j]=dp[i-1][j]+dp[i][j-1]; else if(i>=2) dp[i][j]=dp[i-1][j]; else if(j>=2) dp[i][j]=dp[i][j-1]; //cout<<"i: "<<i<<"j: "<<j<<"dp[i][j]: "<<dp[i][j]<<endl; } } return dp[m][n]; } };Num 62
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); if(obstacleGrid[m-1][n-1]==1) return 0; long dp[105][105]; memset(dp,0,sizeof(dp)); dp[1][1]=1; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(i==1 && j==1) continue; if(obstacleGrid[i-1][j-1]==1) { dp[i][j]=-1; continue; } if(i>=2 && j>=2 && obstacleGrid[i-2][j-1]!=1 && obstacleGrid[i-1][j-2]!=1) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } else if(i>=2 && obstacleGrid[i-2][j-1]!=1) { dp[i][j]=dp[i-1][j]; } else if(j>=2 && obstacleGrid[i-1][j-2]!=1) { dp[i][j]=dp[i][j-1]; } } } return dp[m][n]; } };Num 63