力扣63. 不同路径 II

动态规划

• 思路：
  • 假设 dp[i][j] 是到达第 i 行、第 j 列的路径数量；
  • 因为只能向右或者向下移动，所以状态转移方程：
    • 当v[i][j] = 0时，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；
    • 当v[i][j] = 1时，dp[i][j] = 0；
    • 在第一行中，即 i = 0 时，只能由同一行左边格子路由：
      • 当v[0][j] = 0 时，dp[0][j] = dp[0][j - 1]；
      • 当v[0][j] = 1?时，dp[0][j] = 0；
    • 在第一列中，即 j?= 0 时，只能由同一列上边格子路由：
      • 当v[i][0] = 0 时，dp[i][0] = dp[i - 1][0]；
      • 当v[i][0] = 1?时，dp[i][0] = 0；
  • 边界条件：
    • 当 v[0][0] = 0 时，dp[0][0] = 1；
    • 当 v[0][0] = 1?时，dp[0][0] = 0；

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int row = obstacleGrid.size();
        if (row == 0) {
            return 0;
        }
        int column = obstacleGrid[0].size();
        if (column == 0) {
            return 0;
        }
        std::vector<std::vector<int>> dp(row, std::vector<int>(column));
        if (obstacleGrid[0][0] == 1) {
            dp[0][0] = 0;
        } else {
            dp[0][0] = 1;
        }

        // first column
        for (int i = 1; i < row; ++i) {
            if (obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        // first row
        for (int j = 1; j < column; ++j) {
            if (obstacleGrid[0][j] == 1) {
                dp[0][j] = 0;
            } else {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i < row; ++i) {
            for (int j = 1; j < column; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[row - 1][column - 1];
    }
};

• 空间优化：
  • 本算法空间复杂度为 O(nm)，可以进一步优化成 O(m)，再想一想吧 ... ...