leetcode 63. Unique Paths II DP动态规划

爱被打了一巴掌 2022-06-09 11:42 193阅读 0赞

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 as 1 and 0 respectively 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 is 2.

Note: m and n will be at most 100.

和上一道题题意一样，但是不同的是本题存在“障碍”，遇到障碍就不可行，还是使用动态规划，不过略有不同。

代码如下：

public class Solution 
    {
        /*
         * 这个题和之前的很类似，但是不一样
         * */
        public int uniquePathsWithObstacles(int[][] mat) 
        {
            if(mat==null || mat.length<=0)
                return 0;
            int row=mat.length;
            int col=mat[0].length;
    
            //特殊情况，这种情况其实在后面的动态规划过程中可以包含这种情况
            //但是为了减少运行时间，所以添加这个判断
            if(mat[0][0]==1)
                return 0;
    
            int [][] visit=new int[row][col];
            int i=0;
    
            //初始化动态规划的第一行和第一列的数组
            //要注意的是只要出现一个1，也即表示无法通过，那么接下来都是无法通过
            for(i=0;i<row;i++)
            {
                if(mat[i][0]==1)
                {
                    visit[i][0]=0;
                    break;
                }
                else
                    visit[i][0]=1;
            }
            for(;i<row;i++)
                visit[i][0]=0;
    
    
            //初始化列的数据
            for(i=0;i<col;i++)
            {
                if(mat[0][i]==1)
                {
                    visit[0][i]=0;
                    break;
                }
                else
                    visit[0][i]=1;
            }
            for(;i<col;i++)
                visit[0][i]=0;
    
    
            //动态规划过程
            for(i=1;i<row;i++)
            {
                for(int j=1;j<col;j++)
                {
                    visit[i][j] = (mat[i][j]==1)? 0 : (visit[i-1][j]+visit[i][j-1]);
                }
            }   
            return visit[row-1][col-1];       
        }
    }

下面是C++的做法，和上一道题一样，不过在DP的初始化部分需要注意一下

代码如下:

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& ob)
        {
            if (ob.size() <= 0 || ob[0][0] == 1)
                return 0;
    
            vector<vector<int>> dp;
            for (int i = 0; i < ob.size(); i++)
            {
                vector<int> one(ob[i].size());
                dp.push_back(one);
            }
    
            int row = dp.size();
            int col = dp[0].size();
    
            int i = 0;
            for (i = 0; i < row; i++)
            {
                if (ob[i][0] == 1)
                {
                    dp[i][0] = 0;
                    break;
                }else
                    dp[i][0] = 1;
            }
            for (; i < row; i++)
                    dp[i][0] = 0;
    
            for (i = 0; i < col; i++)
            {
                if (ob[0][i] == 1)
                {
                    dp[0][i] = 0;
                    break;
                }
                else
                    dp[0][i] = 1;
            }
            for (; i < col; i++)
                dp[0][i] = 0;
    
            for (int i = 1; i < row; i++)
            {
                for (int j = 1; j < col; j++)
                    dp[i][j] = ob[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
            }
            return dp[row-1][col-1];
        }
    };