力扣63. 不同路径 II

2023-12-15 05:36:51

动态规划

  • 思路:
    • 假设 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),再想一想吧 ... ...

文章来源:https://blog.csdn.net/N_BenBird/article/details/135006581
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。