动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II

在给定障碍物的二维数组中求解（不新建二维数组，leetcode：时间击败100%用户，内存击败95.57%用户）

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

        int m = obstacleGrid.size(), n = obstacleGrid[0].size();

        // 对首列初始化：无障碍物:初始化为-1，最后返回结果取反即可。有障碍物：数值不变，但其后若有方格，全部初始化为0

        for (int i = 0; i < m; ++i) {

            if (obstacleGrid[i][0] == 1) {

                i++;

                while (i < m) obstacleGrid[i++][0] = 0;

                break;

            }

            obstacleGrid[i][0] = -1;

        }

        for (int i = 0; i < n; ++i) {    // 同理，对首行初始化

            if (obstacleGrid[0][i] == 1) {

                i++;

                while (i < n) obstacleGrid[0][i++] = 0;

                break;

            }

            obstacleGrid[0][i] = -1;

        }

        for (int i = 1; i < m; ++i) {   // 遍历二维网格

            for (int j = 1; j < n; ++j) {

                if (obstacleGrid[i][j] == 1) continue; // 若方格是障碍物(即为1)，则跳过

                if (obstacleGrid[i-1][j] == 1) // 若上方方格为障碍物，则到当前方格的路径数 = 左方方格路径数

                    obstacleGrid[i][j] = obstacleGrid[i][j-1];

                else if (obstacleGrid[i][j-1] == 1) // 同理，左方障碍物，当前 = 上方路径数

                    obstacleGrid[i][j] = obstacleGrid[i-1][j];

                else                                // 左方，上方均无障碍物，则相加

                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];

            }

        }

        if (obstacleGrid[m-1][n-1] == 1) return 0; // 若终点为障碍物，则返回0

        return -obstacleGrid[m-1][n-1]; // 取反即是答案

    }

};