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

分析：

需要注意到题目描述中：机器人只能向下或者向右移动，这一点大大降低了难度。所以可以列出转移方程：

dp[i][j]表示从起点到(i,j)的路径的数量，那么：

dp[i][j] = dp[i-1][j] + dp[i][j-1]  (当这两个点在grid之内且不为障碍物时)

另外，如果(i,j)是障碍物，dp[i][j] = 0

代码如下：

int uniquePathsWithObstacles(vector
   
    
     >& obstacleGrid) {    int height = obstacleGrid.size();    if(height == 0)        return 1;    int width = obstacleGrid[0].size();    vector
     
      
       > dp(height, vector
       
        (width, 0));    if(obstacleGrid[0][0] == 0)  // 起点为障碍物        dp[0][0] = 1;    for(int i = 0; i < height; i++)    for(int j = 0; j < width; j++) {        if(obstacleGrid[i][j] == 1) {            dp[i][j] = 0;        // 目的地为障碍物            continue;        }        if(i > 0 && obstacleGrid[i-1][j] != 1) {            dp[i][j] += dp[i-1][j];        }        if(j > 0 && obstacleGrid[i][j-1] != 1) {            dp[i][j] += dp[i][j-1];        }    }    return dp[height-1][width-1];}
       
      
     
    
   

分析：

与上一题的题型非常相似，可列出状态转移方程：

设dp[i][j]为从左上角到右下角的最短路径的长度，则：

dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i][j]

如果(i,j)不在gird内，dp[i][j] = INT_MAX

如果 (i-1,j),(i,j-1)都不在gird内，则dp[i][j] = grid[i][[j]

代码如下：

int minPathSum(vector
   
    
     >& grid) {    int height = grid.size();    if(height == 0)        return 0;    int width = grid[0].size();    vector
     
      
       > dp(height, vector
       
        (width, 0));    for(int i = 0; i < height; i++)    for(int j = 0; j < width; j++) {        int up = INT_MAX, left = INT_MAX;        if(i > 0)            up = dp[i-1][j];        if(j > 0)            left = dp[i][j-1];        if(i > 0 || j > 0)            dp[i][j] = min(up, left)+grid[i][j];        else            dp[i][j] = grid[i][j];    }    return dp[height-1][width-1];}
       
      
     
    
   

分析：

也是求最短路径，只不过grid的形状为三角形，以及目的地不止一个，大同小异。不过可以尝试达到O(n)的空间复杂度。

设dp[i,j]为从起点到达(i,j)的最短路径，则有转移方程：

dp[i,j] = min(dp[i-1] [j-1], dp[i-1][j]) + triangle[i][j];

如果(i,j)不在grid内，则dp[i][j] = INT_MAX

如果(i-1,j-1)和(i-1,j)都不在grid内，则dp[i][j] = triangle[i][j]

然后就是两层for循环解决问题。

以上是使用二维dp数组，空间复杂度为,要达到空间复杂度，首先直接把前一维i去掉，也就是每次都重复使用同一个dp数组。那么问题来了，因为后一层dp运算需要用到前一层的结果，那么在运算的过程中就不能把这些值提前覆盖了，解决办法就是：将j的循环逆向。

代码如下：

int minimumTotal(vector
   
    
     >& triangle) {    int height = triangle.size();    if(height == 0)        return 0;    int width = height;    vector
     
       dp(width, 0);    for(int i = 0; i < height; i++)    for(int j = i; j >= 0; j--) {        int left = INT_MAX, right = INT_MAX;        if(j > 0)            left = dp[j-1];        if(j < i)            right = dp[j];        if(j == 0 && i == 0)            left = right = 0;        dp[j] = min(left, right) + triangle[i][j];    }    sort(dp.begin(), dp.end());    return dp[0];}
     
    
   

转载地址：http://jwwob.baihongyu.com/