算法刷题记录 Day34

Date: 2024.03.30

lc 63. 不同路径II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& G) {
        // dp[i][j]表示从（0，0）到（i,j）的路径数；
        // dp[i][j] = dp[i-1][j] + dp[i][j-1] if G(i,j)!=1 else dp[i][j] = 0;
        // dp[0][j] = dp[0][j-1]; ifG(0,j) = 1,dp[0][j] = 0;
        int m = G.size();
        int n = G[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        for(int i=0; i<m; i++){
            if(G[i][0] == 1)
                break;
            dp[i][0] = 1;
        }

        for(int j=0; j<n; j++){
            if(G[0][j] == 1)
                break;
            dp[0][j] = 1;
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(G[i][j] == 1){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    //cout<<"i:"<<i<<" j:"<<j<<" dp:"<<dp[i][j]<<endl;
                }
            }
        }
        return dp[m-1][n-1];

    }
};

lc 62. 不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp[i][j] 表示从（0，0）到（i,j）的路径数；
        // dp[i][j] = dp[i-1][j] + dp[i][j-1];
        // dp[i][0] = 1; dp[0][j] = 1;
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                //cout<<"(i, j):"<<i<<","<<j<<"dp[i][j]:"<<dp[i][j]<<endl;
            }
        }
        return dp[m-1][n-1];

    }
};