LeetCode 63 不同路径 II

dfs(超时)

class Solution {
public:
    int res = 0;
    void dfs(int i, int j, vector<vector<int>>& obstacleGrid) {
        if (i == obstacleGrid.size() - 1 && j == obstacleGrid[0].size() - 1) res ++;

        if (i + 1 < obstacleGrid.size() && obstacleGrid[i + 1][j] != 1) dfs(i + 1, j, obstacleGrid);
        if (j + 1 < obstacleGrid[0].size() && obstacleGrid[i][j + 1] != 1) dfs(i, j + 1, obstacleGrid);
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;
        dfs(0, 0, obstacleGrid);

        return res;
    }
};

动态规划

const int N = 110;
class Solution {
public:
    int dp[N][N];
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;

        for (int i = 0; i < obstacleGrid.size(); i ++) {
            if (obstacleGrid[i][0] == 1) { //当边界上有障碍物，该边界以后都达不到
                dp[i][0] = 0;
                break;
            } 
            else dp[i][0] = 1;
        }
        for (int j = 0; j < obstacleGrid[0].size(); j ++) {
            if (obstacleGrid[0][j] == 1) { //当边界上有障碍物，该边界以后都达不到
                dp[0][j] = 0;
                break;
            }
            else dp[0][j] = 1;
        } 

        for (int i = 1; i < obstacleGrid.size(); i ++)
            for (int j = 1; j < obstacleGrid[0].size(); j ++) {
                if (obstacleGrid[i][j] != 1) 
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else dp[i][j] = 0; //遇到障碍物dp[i][j]为0
            }
        
        return dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};