动态规划——unique-paths-ii

最新推荐文章于 2024-11-09 14:01:33 发布

井底的笨鸟

最新推荐文章于 2024-11-09 14:01:33 发布

阅读量431

点赞数

分类专栏： LeetCode

本文链接：https://blog.csdn.net/jingsuwen1/article/details/51483931

版权

LeetCode 专栏收录该内容

97 篇文章

订阅专栏

题目描述：

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as1and0respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is2.

Note: m and n will be at most 100.

递归例程：

public class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        if(grid == null||grid.length == 0||grid[0].length == 0)
            return 0;
        int row=grid.length;
        int col=grid[0].length;
        return help(grid,0,0,row,col);
    }
    public int help(int[][] grid,int i,int j,int row,int col)
        {
        if(i == row-1&&j == col-1)
            return 1;
        if(grid[i][j] == 1)
            return 0;
        if(i == row-1)
            return help(grid,i,j+1,row,col);
        if(j == col-1)
            return help(grid,i+1,j,row,col);
        else
            return help(grid,i+1,j,row,col)+help(grid,i,j+1,row,col);
    }
}

DP例程：

 public int uniquePathsWithObstacles(int[][] grid) {
        if(grid == null||grid.length == 0||grid[0].length == 0)
            return 0;
        int row=grid.length;
        int col=grid[0].length;
        int[][] dp=new int[row][col];
        dp[row-1][col-1]=1;
        if(grid[row-1][col-1] == 1)
            dp[row-1][col-1]=0;
        //最下行初始化
        for(int j=col-2;j>=0;j--)
            {
            if(grid[row-1][j] == 1)
                dp[row-1][j]=0;
            else
                dp[row-1][j]=dp[row-1][j+1];
        }
        //最右行初始化
        for(int i=row-2;i>=0;i--)
            {
            if(grid[i][col-1] == 1)
                dp[i][col-1]=0;
            else
                dp[i][col-1]=dp[i+1][col-1];
        }
        //general
        for(int i=row-2;i>=0;i--)
            {
            for(int j=col-2;j>=0;j--)
                {
                if(grid[i][j] == 1)
                    dp[i][j]=0;
                else
                    dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[0][0];
    }