力扣:63. 不同路径 II

63. 不同路径 II

一个机器人位于一个 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
class Solution {public int uniquePathsWithObstacles(int[][] ob) {int m = ob.length;int n = ob[0].length;int[][] dp = new int[m][n];int flag = 0;for(int i = 0;i < m;i++){if(ob[i][0]==1||flag==1){//当第一列有障碍时,那么他后面的路径就为0了,因为走不通dp[i][0] = 0;flag = 1;}else{dp[i][0] = 1;//没有障碍,路径为1}}flag = 0;for(int i = 0;i < n;i++){if(ob[0][i]==1||flag==1){//同理dp[0][i] = 0;flag = 1;}else{dp[0][i] = 1;}}if(m==1||n==1)return dp[m-1][n-1];//排除行列为1的情况for(int i = 1;i < m;i++){for(int j = 1;j < n;j++){if(ob[i][j]==1){dp[i][j] = 0;//若有障碍,则路径为0}else{dp[i][j] = dp[i-1][j] + dp[i][j-1];//否则为左方和上方之和,因为只能由左边和上面推导而来}}}return dp[m-1][n-1];//返回右下角的路径数}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3014998.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

C# Web控件与数据感应之 BaseDataList 类

目录 关于数据感应 BaseDataList 类 范例运行环境 pageview 方法 设计 实现 调用示例 数据源 调用 小结 关于数据感应 数据感应也即数据捆绑&#xff0c;是一种动态的&#xff0c;Web控件与数据源之间的交互&#xff0c;本文将继续介绍以与数据库提取数据并捆绑控件…

CI522/CI523电动车NFC一键启动开发资料

Ci522是一颗工作在13.56MHz频率下的非接触式读写芯片&#xff0c;支持读A卡&#xff08;CI523支持读A/B卡&#xff09;&#xff0c;可做智能门锁、电动车NFC一键启动、玩具NFC开锁等应用。为部分要求低成本&#xff0c;PCB小体积的产品提供了可靠的选择。 Ci522与Si522/MFRC52…

第3章 WebServer重构

3.1 重构原生Web服务框架 3.1.1 分析原生Web服务框架 在服务端代码的 ClientHandler 中&#xff0c;请求解析、处理请求、返回响应的代码混杂在一起&#xff0c;这样的设计会导致代码难以维护和理解。为了提高代码的可读性、可维护性和可扩展性&#xff0c;我们需要对这些代码…

UDP广播

1、UDP广播 1.1、广播的概念 广播&#xff1a;由一台主机向该主机所在子网内的所有主机发送数据的方式 例如 &#xff1a;192.168.3.103主机发送广播信息&#xff0c;则192.168.3.1~192.168.3.254所有主机都可以接收到数据 广播只能用UDP或原始IP实现&#xff0c;不能用TCP…

漏洞挖掘 | EDU证书站任意密码重置

1.前言&#xff1a; 挖了一段时间EDU老破小的站&#xff0c;也该拿证书站下手了。下手的第一个目标&#xff0c;那必然是漏洞排行榜第一的某交大&#xff01;&#xff01;&#xff01; 2.信息搜集 想快速挖到漏洞&#xff0c;必须信息搜集全面。如果信息搜集不到位不全面&…

明星中药企业系列洞察(二)丨百年御药同仁堂,为什么被称为我国最“硬”的老字号?

从最初的同仁堂药室、同仁堂药店到现在的北京同仁堂集团&#xff0c;经历了清王朝由强盛到衰弱、几次外敌入侵、军阀混战到新民主主义革命的历史沧桑&#xff0c;其所有制形式、企业性质、管理方式也都发生了根本性的变化&#xff0c;但同仁堂经历数代而不衰&#xff0c;在海内…

蓝桥杯练习系统(算法训练)ALGO-947 贫穷的城市

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 某城市有n个小镇&#xff0c;编号是1~n。由于贫穷和缺乏城市规划的人才&#xff0c;每个小镇有且仅有一段单向的公路通往别…

[Linux] GDB使用指南----包含CentOS7下安装以及使用

什么是GDB&#xff1f; GDB 是由 GUN 软件系统社区提供的调试工具&#xff0c;同 GCC 配套组成了一套完整的开发环境&#xff0c;GDB 是 Linux 和许多 类Unix系统的标准开发环境。可以用来调试C、C、Go、java、 objective-c、PHP等语言。 GDB的作用 程序启动时&#xff0c;可…

400 Bad Request问题

总结&#xff1a;请求路径写错了 400 问题 原地址&#xff0c;deleteSetmeal的参数应该改为param 更改请求地址正确后即可

视频质量评估

视频质量评估 一、全参考客观视频质量评价方法三、MSSIM四、STRRED五、VMAF六、MOS 一、全参考客观视频质量评价方法 全参考客观视频质量评价方法是指把原始参考视频与失真视频在每一个对应帧中的每一个对应像素之问进行比较。准确的讲&#xff0c;这种方法得到的并不是真正的…

Chromium编译指南2024 Windows11篇-Git工具准备(四)

前言 在《Chromium编译指南2024&#xff08;三&#xff09;》中&#xff0c;我们已经完成了对 Chromium 编译环境的其他相关环境变量的设置&#xff0c; 接下来&#xff0c;我们将进一步探讨如何初始化配置 Git&#xff0c;为获取 Chromium 源代码做好准备。 1. 配置Git 用户…

AI伦理和安全风险管理终极指南

人工智能&#xff08;AI&#xff09;正在迅速改变各个领域的软件开发和部署。驱动这一转变的两个关键群体为人工智能开发者和人工智能集成商。开发人员处于创建基础人工智能技术的最前沿&#xff0c;包括生成式人工智能&#xff08;GenAI&#xff09;模型、自然语言处理&#x…

VBA在Excel中字母、数字的相互转化

VBA在Excel中字母、数字的相互转化 字母转数字的方法 数字转字母的方法 众所周知,Excel表中的行以数字展示,列用字母展示,如下图: 编程时,很多时候需要将列的字母转变为数字使用,如cells(num1,num2).value等,不知大家是怎么将字母转化为数字的,Excel是否有其他方式…

今天看到一个有意思的问题:个人网站被恶意大量访问,怎么办(文末附GPT指令优化)

目录 问题描述 一、GPT 3.5 二、通义千问 三、讯飞星火 四、文心一言 五、Kimi 六、智谱清言 个人分析&#xff1a; 问题描述 大家好&#xff01;我的个人网站每天晚上7点30到11点被固定的十几个IP大量下载exe&#xff0c;造成网站带宽不够&#xff0c;怎么办! 已经把…

耕耘未来——揭秘第一产业的无限潜能

在浩瀚的科技宇宙中&#xff0c;当火星探测器的每一次着陆都能激起全球狂欢&#xff0c;当虚拟现实的浪潮让我们触碰未来&#xff0c;有一个领域&#xff0c;以其恒久不变的坚韧&#xff0c;默默地滋养着人类文明的根脉——这就是第一产业&#xff0c;那片古老而又充满生机的土…

护眼灯有没有护眼的效果?一键查看这五大护眼效果极佳的护眼台灯

在数字时代&#xff0c;护眼灯已成为保护视力的重要工具。但消费者常问&#xff1a;护眼灯有没有护眼的效果&#xff1f;挑选到技术过关的护眼台灯是能够很好地起到护眼效果的。本文将并重点介绍五款具有卓越护眼功能的台灯。这些精选灯具不仅在照明效果上表现出色&#xff0c;…

C#里如何设置输出路径,不要net7.0-windows

官网介绍&#xff1a; 更改生成输出目录 - Visual Studio (Windows) | Microsoft Learn <PropertyGroup> <AppendTargetFrameworkToOutputPath>false</AppendTargetFrameworkToOutputPath> <AppendRuntimeIdentifierToOutputPath>false</Appen…

10000字讲解IoC 思想以及五大注解

文章目录 IoC 思想通过案例讲解 IoC1.传统的开发方式 SpringIoC 和 DI五大注解ControllerServiceComponentRepositoryConfiguration 为什么要有这么多的类注解类注解之间的关系方法注解 Bean重命名 bean扫描路径 IoC 思想 什么是 Spring 呢&#xff1f; 我们经常听到的都是说…

如何使用 iOS系统恢复软件修复 iPhone 问题

苹果公司向世界推出了他们可以拥有的最智能的手机。但即使是 iPhone 也无法避免智能手机常见的损坏和问题。您将熟悉最常见的问题。屏幕黑屏或卡在 Apple 徽标上&#xff1b;冻结或卡在恢复模式的 iPhone。但这样的问题不胜枚举&#xff0c;每天都有 iOS 用户在他们的设备中遇到…

微信小程序知识点归纳(一)

前言&#xff1a;适用于有一定基础的前端开发同学&#xff0c;完成从网页开发到小程序开发的知识转换。 先立框架&#xff0c;后砌墙壁 回顾&#xff1a;了解微信小程序开发流程-CSDN博客 初始页面结构&#xff0c;三部分pages、utils、配置&#xff0c;分别存放页面、工具类…