63. 不同路径 II(leetcode)

简单dp
https://leetcode.cn/problems/unique-paths-ii/description/

传统做法:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int f[110]={0}; // 优化一维
        f[1]=1;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(obstacleGrid[i-1][j-1] == 1)f[j]=0;
                else f[j]=f[j]+f[j-1];
            }
        }
        return f[n];
    }
};

搜索做法:

class Solution {
public: 
    int ans=0;
    int w[110][110]={0};
    int backup[110][110]={0};
    int m=0,n=0;
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        for(int i=1;i<=obstacleGrid.size();i++)
            for(int j=1;j<=obstacleGrid[0].size();j++)
                w[i][j]=obstacleGrid[i-1][j-1];
        m=obstacleGrid.size();
        n=obstacleGrid[0].size();
        return dfs(m,n);
        
    }
    // 倒序记搜实现dp
    int dfs(int x, int y)
    {
        if(x<0 || x>m || y<0 || y>n)return 0;
        if(backup[x][y] != 0)return backup[x][y];
        if(w[x][y]==1)return 0;
        if(x == 1 && y == 1)
        {
            return 1; // 得到答案
        }
        backup[x][y] = dfs(x-1,y)+dfs(x,y-1); // f[i][j]=f[i-1][j]+f[i][j-1]
        return backup[x][y];
    }

};