leetcode 不同路径II

佚名 6年前 (2019-05-08) 随笔 1637人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

二维数组动态规划,还可以采用一维数组进行动态规划。

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