Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Unique Paths II

Leetcode algorithms 第 63 题:Unique Paths II。

题目

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 3×3 grid as illustrated below.

The total number of unique paths is 2.

Note: m and n will be at most 100.

解答

从左上角走到右下角的走法数,每次只能向下或向右。使用动态规划,dp[i][j]表示从第i行第j列开始的走法数,由于只能向右或向下,于是

dp[i][j] = dp[i+1][j] + dp[i][j+1]

当然,这是理想情况,实际需要考虑边界溢出或者某个位置有障碍物挡住的情况。

具体代码如下:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &v) {
        if (v.empty() || v[0].empty()) return 0;
        
        int m = v.size(), n = v[0].size();
        if (v[0][0] == 1 || v[m-1][n-1] == 1) return 0;
        
        vector<vector<int>> dp(m, vector<int>(n, 0)); //初始化为0
        for (int i = m-1; i >= 0; i--)
            for (int j = n-1; j >= 0; j--)
            {
                if (v[i][j] == 1) continue; //有障碍物
                
                if (i == m-1 && j == n-1) dp[i][j] = 1; //边界上
                else
                {
                    if (i+1 < m && v[i+1][j] == 0) dp[i][j] += dp[i+1][j];
                    if (j+1 < n && v[i][j+1] == 0) dp[i][j] += dp[i][j+1];
                }
            }
        return dp[0][0];
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论