矩形路径问题

62. 不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        dp[1][1] = 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                dp[i][j] += dp[i-1][j] + dp[i][j-1];
        return dp[n][m];
    }
};

63. 不同路径 II

需要注意的是 1 不能被走到！当前位置为 1 时不能被走到

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        vector<vector<int>> dp(n, vector<int>(m));
        if (obstacleGrid[0][0] == 1) return 0;
        dp[0][0] = 1;
        for (int i = 1; i < n; i ++)
            if (obstacleGrid[i][0] != 1 && obstacleGrid[i-1][0] != 1)
                dp[i][0] = dp[i-1][0];
        for (int i = 1; i < m; i ++)
            if (obstacleGrid[0][i] != 1 && obstacleGrid[0][i-1] != 1)
                dp[0][i] = dp[0][i-1];

        for (int i = 1; i < n; i ++)
            for (int j = 1; j < m; j ++)
            {
                if (obstacleGrid[i][j] == 1) continue;
                if (obstacleGrid[i-1][j] != 1)
                    dp[i][j] += dp[i-1][j];
                if (obstacleGrid[i][j-1] != 1)
                    dp[i][j] += dp[i][j-1];
            }

        return dp[n-1][m-1];
    }
};