C++实现LeetCode(63.不同的路径之二)

 更新时间:2021年7月17日 00:00  
这篇文章主要介绍了C++实现LeetCode(63.不同的路径之二),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

[LeetCode] 63. Unique Paths II 不同的路径之二

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

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.

Note: m and n will be at most 100.

Example 1:

Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

这道题是之前那道 Unique Paths 的延伸,在路径中加了一些障碍物,还是用动态规划 Dynamic Programming 来解,使用一个二维的 dp 数组,大小为 (m+1) x (n+1),这里的 dp[i][j] 表示到达 (i-1, j-1) 位置的不同路径的数量,那么i和j需要更新的范围就是 [1, m] 和 [1, n]。状态转移方程跟之前那道题是一样的,因为每个位置只能由其上面和左面的位置移动而来,所以也是由其上面和左边的 dp 值相加来更新当前的 dp 值,如下所示:

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

这里就能看出来初始化 d p数组的大小为 (m+1) x (n+1),是为了 handle 边缘情况,当i或j为0时,减1可能会出错。当某个位置是障碍物时,其 dp 值为0,直接跳过该位置即可。这里还需要初始化 dp 数组的某个值,使得其能正常累加。当起点不是障碍物时,其 dp 值应该为1,即dp[1][1] = 1,由于其是由 dp[0][1] + dp[1][0] 更新而来,所以二者中任意一个初始化为1即可。由于之后 LeetCode 更新了这道题的 test case,使得使用 int 型的 dp 数组会有溢出的错误,所以改为使用 long 型的数组来避免 overflow,代码如下:

解法一:

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

或者我们也可以使用一维 dp 数组来解,省一些空间,参见代码如下:

解法二:

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

到此这篇关于C++实现LeetCode(63.不同的路径之二)的文章就介绍到这了,更多相关C++实现不同的路径之二内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!

相关文章

  • 深入学习C++智能指针之shared_ptr与右值引用的方法

    智能指针的核心实现技术是引用计数,每使用它一次,内部引用计数加1,每析构一次内部的引用计数减1,减为0时,删除所指向的堆内存,今天通过本文给大家分享C++智能指针之shared_ptr与右值引用的方法,需要的朋友跟随小编一起看看吧...2021-07-13
  • C++字符串的处理详解

    这篇文章主要介绍了C++ string字符串类,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-08-13
  • 浅谈C++类型转换几种情况

    本文主要介绍了几种C++类型转换,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-08-05
  • C++实现LeetCode(37.求解数独)

    这篇文章主要介绍了C++实现LeetCode(37.求解数独),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • C++ const关键字分析详解

    C++中的const关键字的用法非常灵活,而使用const将大大改善程序的健壮性。这篇文章主要介绍了C/C++ 中const关键字的用法,需要的朋友可以参考下...2021-08-29
  • C/C++中虚基类详解及其作用介绍

    这篇文章主要介绍了C/C++中虚基类的详解及其作用介绍,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
  • C++变量引用的概念介绍

    这篇文章主要介绍了C++变量引用的概念介绍,简单提到了与指针概念的不同,通过代码场景分析给大家介绍的非常详细,需要的朋友可以参考下...2021-08-04
  • 一文搞懂C++中的四种强制类型转换

    很多朋友向小编了解C语言中怎么进行强制类型转换呢?在这小编告诉大家强制类型转换可以分为两种,一种是隐式类型转换一种是显示类型转换,下面通过示例代码给大家介绍下,需要的朋友参考下吧...2021-07-07
  • C++中char[]能修改char*却不行

    本文主要介绍了C++中char[]能修改char*却不行,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-13
  • C++:构造函数,析构函数详解

    今天小编就为大家分享一篇关于C++构造函数和析构函数的文章,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧...2021-09-01
  • 一篇文章带你了解C++智能指针详解

    这篇文章主要介绍了c++ 智能指针基础的相关资料,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下,希望能给你带来帮助...2021-08-13
  • C++实现矩阵对称正交化的示例代码

    这篇文章主要介绍了C++实现矩阵对称正交化,分为python代码和C++的eigen库实现代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-15
  • C++ 约瑟夫环问题案例详解

    这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
  • 结构体对齐的规则详解及C++代码验证

    在c语言的结构体里面一般会按照某种规则去进行字节对齐。本文就来介绍一下如何实现,具有一定的参考价值,感兴趣的可以了解下...2021-08-17
  • 线段树详解以及C++实现代码

    线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中,这篇文章主要给大家介绍了关于线段树以及C++实现的相关资料,需要的朋友可以参考下...2021-07-19
  • C++实现LeetCode(51.N皇后问题)

    这篇文章主要介绍了C++实现LeetCode(51.N皇后问题),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • 从c++标准库指针萃取器谈一下traits技法(推荐)

    本篇文章基于gcc中标准库源码剖析一下标准库中的模板类pointer_traits,并且以此为例理解一下traits技法,对c++ traits技法源码分析感兴趣的朋友跟随小编一起看看吧...2021-07-14
  • C++手写内存池的案例详解

    这篇文章主要介绍了C++手写内存池的案例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-08-08
  • C/C++实现快速排序(两种方式)图文详解

    这篇文章主要介绍了C/C++实现快速排序的方法,这几天在找工作,被问到快速排序,结果想不出来快速排序怎么弄的;回来搜索了一下,现在记录下来,方便以后查看...2021-08-13
  • C++ 实现桶排序的示例代码

    桶排序或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子,本文详细的介绍了如何实现,感兴趣的可以了解一下...2021-07-12