一、题目描述

二、解题思路

进阶版的不同路径，dp来解答，很明显是二维动态规划

定义dp含义：定义 $d p [i] [j]$ 为走到坐标为 $(i, j)$ 这一点的走法
定义边界条件
- 首行首列上没有障碍物的情况下，首行首列肯定都是1的了，因为只能有一种走法
- 但是，如果首行首列上有障碍物，那么最远只能走到障碍物的前面，包括障碍物所在的那一点及其后面的dp的值都是0
建立状态转移方程
- 假设当前机器人位于 $(i, j)$ ，默认dp[i][j] = 0;
  - 如果该点有障碍物，那么dp[i][j]只能为0
  - 如果该点没有障碍物
    - 上面的点
      - 有障碍物，那么上面的路被堵死，只能从左边过来，那么dp[i][j]不变，加上0
      - 没有障碍物，可以从上面过来，那么dp[i][j] += dp[i - 1][j]
      - 整理：dp[i][j] += (obstacleGrid[i][j - 1] ? 0 : dp[i][j - 1]);
    - 左边的点
      - 同理：dp[i][j] += (obstacleGrid[i - 1][j] ? 0 : dp[i - 1][j]);

三、解题代码

class Solution {
   
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
   
        auto m = obstacleGrid.size();
        auto n = obstacleGrid[0].size();
        unsigned int dp[m][n];

        bool flag = 0;
        for(int i = 0; i < m; i++){
   
            if(!obstacleGrid[i][0] && !flag)
                dp[i][0] = 1;
            else{
   
                dp[i][0] = 0;
                flag = 1;
            }   
        }

        flag = 0;
        for(int i = 0; i < n; i++){
   
            if(!obstacleGrid[0][i] && !flag)
                dp[0][i] = 1;
            else{
   
                dp[0][i] = 0;
                flag = 1;
            }
        }
        
        for(int i = 1; i < m; i++){
   
            for(int j = 1; j < n; j++){
   
                dp[i][j] = 0;
                if(obstacleGrid[i][j] == 0){
   
                    if(obstacleGrid[i][j - 1] == 0)
                    dp[i][j] += (obstacleGrid[i][j - 1] ? 0 : dp[i][j - 1]);
                    if(obstacleGrid[i - 1][j] == 0)
                        dp[i][j] += (obstacleGrid[i - 1][j] ? 0 : dp[i - 1][j]);
                }             
            }
        }
        return dp[m - 1][n - 1];
    }
};

四、运行结果

有一组运行结果很是嚣张：

[[0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0],[1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,1],[0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],[0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0],[1,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0],[0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0],[0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],[1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0],[0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,1],[0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1],[1,1,1,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1],[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0]]

直接导致我数据溢出，这个故事告诉我们要把dp数组设置成unsigned int型，避免溢出

LeetCode-63：不同路径II

一、题目描述

二、解题思路

三、解题代码

四、运行结果