草庐IT

【Leetcode】63. 不同路径 II

顾北清 2023-03-28 原文

题目（链接）

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用1和0来表示。

示例1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

题解

思路：

  • 动态规划
  • 终点位置可以从上面过来或者从左边过来，所以计算从上面过来的路径数+从左边过来的路径数就可以得到总的路径数。
  • 特殊判断第一行和第一列，因为这两个位置只有一种走的方案，即第一行只能从左边过来，第一列只能从上面过来。
  • 特判有障碍的位置，有障碍的位置是无法到达的，所以初始化第一行和第一列的时候只需要初始化不为1的部分，而且一旦遇到障碍，障碍后面的位置均为0.

code:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        int f[n + 10][m + 10];
        memset(f, 0, sizeof f);
        // 当不满足判断条件i < n && obstacleGrid[i][0] == 0时，跳出循环
        // 这样一旦遇到障碍，后面的值还是0，只初始化障碍前的位置为1
        for (int i = 0; i < n && obstacleGrid[i][0] == 0; i ++){
            f[i][0] = 1;
        }
        for (int j = 0; j < m && obstacleGrid[0][j] == 0; j ++){
            f[0][j] = 1;
        }

        for (int i = 1; i < n; i ++){
            for (int j = 1; j < m; j ++){
                // 如果当前位置不是障碍则可以进行计算
                // 如果是障碍，则不计算，默认还是0，即没有方案到达
                if (obstacleGrid[i][j] == 0){
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }

        return f[n - 1][m - 1];
    }
};
Leetcode63obstacleGridcode障碍算法与数据结构

有关【Leetcode】63. 不同路径 II的更多相关文章

  1. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. java - 为什么 ruby​​ modulo 与 java/other lang 不同？ - 2

    我基本上来自Java背景并且努力理解Ruby中的模运算。(5%3)(-5%3)(5%-3)(-5%-3)Java中的上述操作产生，2个-22个-2但在Ruby中，相同的表达式会产生21个-1-2.Ruby在逻辑上有多擅长这个？模块操作在Ruby中是如何实现的？如果将同一个操作定义为一个web服务，两个服务如何匹配逻辑。 最佳答案 在Java中，模运算的结果与被除数的符号相同。在Ruby中，它与除数的符号相同。remainder()在Ruby中与被除数的符号相同。您可能还想引用modulooperation.

  4. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  5. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  6. ruby-on-rails - 如何用不同的用户运行nginx主进程 - 2

    A/ctohttp://wiki.nginx.org/CoreModule#usermaster进程曾经以root用户运行，是否可以以不同的用户运行nginxmaster进程？ 最佳答案 只需以非root身份运行init脚本(即/etc/init.d/nginxstart)，就可以用不同的用户运行nginxmaster进程。如果这真的是你想要做的，你将需要确保日志和pid目录(通常是/var/log/nginx&/var/run/nginx.pid)对该用户是可写的，并且您所有的listen调用都是针对大于1024的端口(因为绑定(

  7. ruby-on-rails - 如何播种图像的路径？ - 2

    Organization和Image具有一对一的关系。Image有一个名为filename的列，它存储文件的路径。我在Assets管道中包含这样一个文件:app/assets/other/image.jpg。播种时如何包含此文件的路径？我已经在我的种子文件中尝试过:@organization=...@organization.image.create!(filename:File.open('app/assets/other/image.jpg'))#Ialsotried:#@organization.image.create!(filename:'app/assets/other/i

  8. ruby - 从 sinatra 中的 before do block 返回不同的值 - 2

    有没有办法在sinatra的beforedoblock中停止执行并返回不同的值？beforedo#codeishere#Iwouldliketo'return"Message"'#Iwouldlike"/home"tonotgetcalled.end//restofthecodeget'/home'doend 最佳答案 beforedohalt401,{'Content-Type'=>'text/plain'},'Message!'end如果你愿意，你可以只指定状态，这里有状态、标题和正文的例子

  9. ruby-on-rails - Sunspot:如何对具有不同值的多个字段进行全文查询？ - 2

    我想用sunspot重现以下原始solr查询q=exact_term_text:fooORterm_textv:foo*ORalternate_text:bar*但我无法通过标准的太阳黑子界面理解这是否可能以及如何实现，因为看起来:fulltext方法似乎不接受多个文本/搜索字段参数我不知道将什么参数作为第一个参数传递给fulltext，就好像我通过了"foo"或"bar"结果不匹配如果我传递一个空参数，我得到一个q=*:*范围过滤器(例如with(:term).starting_with('foo*')(顾名思义)作为过滤器查询应用，因此不参与评分。似乎可以手动编写字符串(或者可能使

  10. ruby - 拆分字符串并分配给不同的变量 - 2

    我从ui中得到日期范围为-approved_between"=>"2013-03-17-2013-03-18"我需要拆分此approved_start_date="2013-03-17"和approved_end_date="2013-03-18"...我希望使用它在mysql中查询，因为mysql中的日期格式是created_at:2012-07-2810:35:01.我正在做的是:approved=approved_between.split("")approved_start_date=approved[0]approved_end_date=approved[2]很确定这不是处

随机推荐