LeetCode 62. Unique Paths LeetCode 63 Unique Paths II 不同的路径之二-白红宇

LeetCode 62. Unique Paths LeetCode 63 Unique Paths II 不同的路径之二

阅读量：3503 次

发布时间：2019-05-20

本文共 1472 字，大约阅读时间需要 4 分钟。

初识动态规划。

格点(i,j)。由于只能从上格点(i-1,j)或左格点(i,j-1)到达，并且两者路径是不重复的

因此path[i][j] = path[i-1][j]+path[i][j-1]。

最近要开始看动态规划了。

class Solution {public:    int uniquePaths(int m, int n) {        vector
   
    
     > ans(m,vector
     
      (n,1));        for(int i=1;i

63II 自己写的方法1特复杂。

class Solution {public:    int uniquePathsWithObstacles(vector
   
    
     >& obstacleGrid) {        //obstacleGrid={
  {0,0,0},{0,1,0},{0,0,0}};        int m=obstacleGrid.size();        int n=obstacleGrid[0].size();        int i,j,j1,i1;        vector
     
      
       > ans(m,vector
       
        (n,1));        if(m>=1&&n>=1)        {                           for(j=0;j

方法2：

class Solution {public:    int uniquePathsWithObstacles(vector
   
    
     >& obstacleGrid) {        if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;        vector
     
      
        > dp(obstacleGrid.size(), vector
       
        (obstacleGrid[0].size(), 0));        for (int i = 0; i < obstacleGrid.size(); ++i) {            for (int j = 0; j < obstacleGrid[i].size(); ++j) {                if (obstacleGrid[i][j] == 1) dp[i][j] = 0;                else if (i == 0 && j == 0) dp[i][j] = 1;                else if (i == 0 && j > 0) dp[i][j] = dp[i][j - 1];                else if (i > 0 && j == 0) dp[i][j] = dp[i - 1][j];                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];            }        }        return dp.back().back();    }};