【动态规划】06路径问题_不同路径II_C++(medium)

题目链接:leetcode不同路径II


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求在考虑网格中有障碍物的情况下,从左上角到右下角将会有多少条不同的路径

由题可得:

机器人位于一个 m x n 网格的左上角 

机器人每次只能向下或者向右移动一步

我们拿示例1来分析:

则根据题目要求我们只能向下或者向右移动一步,不能向上或向左回退,而且要避开障碍物;

所以这里我们一共有2种走法:


算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义(是什么?)

dp[i][j]表示到达i*j时一共有多少种方式;

这种状态表示怎么来的?

1..经验+题目要求

用之前或者之后的状态,推导出dp[i][j]的值;

根据最近的最近的一步,来划分问题

经验:以i*j位置为结尾,

题目让我们求到达右下角有多少种方式(需要避开障碍物),那么这里我们可以dp[i][j]来表示。

所以这里我们用i*j表示右下角位置;

2.状态转移方程

dp[i]等于什么?

 我们先不考虑有障碍物的情况:

当机器人到达dp[i-1][j]时,我们知道它到达[i-1][j]有dp[i-1][j]方式,

此时只需要从[i-1][j]往下走一步就可以到达目标位置,即:

……-->[i-1][j]-->(往下走一步)[i][j];

……-->[i-1][j]-->(往下走一步)[i][j];

……-->[i-1][j]-->(往下走一步)[i][j];

……

所以往下走一步就可以到达目标位置的方式就有dp[i-1][j]种;

那么同理,

当机器人到达dp[i][j-1]时,我们知道它到达[i][j-1]有dp[i][j-1]方式,

此时只需要在到达[i][j-1]方式的后面往右边走一步就可以到达目标位置,即:

……-->[i][j-1]-->(往右边走一步)[i][j];

……-->[i][j-1]-->(往右边走一步)[i][j];

……-->[i][j-1]-->(往右边走一步)[i][j];

……

所以往右边走一步就可以到达目标位置的方式就有dp[i-1][j]种;

综上所述,我们只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到,到达[i][j]位置的总方法,

即:

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

好,分析完了没有障碍物的情况,现在我们再来加上障碍物:

从上面的分析我们知道到达i*j位置,只要将到达[i][j-1]与[i-1][j]的总方法相加即可得到

如果[i][j-1]与[i-1][j]之中有一个是障碍物时:

那么有效的路线就只有上面那条,那么只要把有障碍物的地方设为0,就不会影响状态转移方程了。

3.初始化

(保证填表的时候不越界)

 由我们的状态转移方程得:

在0行0列的时候越界,所以我们这里可以在m*n的外围多加1行1列,如图:

还有一个问题是:

我们要拿新增用来初始化的行和列要初始化为几呢?

假设:如果所需要到达的位置就在机器人所在的位置,此时有一种方式

根据状态转移方程,在[0][1]与[1][0]位置要有一个位置需要初始化为1,其他位置初始化为0

我们这里选择[0][1]初始化为1

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:到达该位置的上面和左边位置的方式

所以填表顺序:

从上到下填写每一行

从左到右填写每一列

5.返回值

(根据题目要求和状态表示)

综上分析:

返回值为:dp[m][n];


编写代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    //1.创建dp表
    //2.初始化
    //3.填表
    //4.返回结果
    int m=obstacleGrid.size();
    int n=obstacleGrid[0].size();
    vector<vector<int>> dp(m+1,vector<int>(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]==1)
            {
                dp[i][j]=0;
            }
            else
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    return dp[m][n];
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JVM虚拟机系统性学习-垃圾回收器CMS、G1和ZGC

CMS&#xff1a;低延迟 在 JDK1.5 时&#xff0c;HotSpot 推出了 CMS 收集器&#xff0c;CMS 收集器是 HotSpot 虚拟机中第一款真正意义上的并发收集器&#xff0c;它第一次实现了让垃圾收集线程和用户线程同时工作CMS 收集器关注尽可能地降低用户线程的停顿时间&#xff0c;停…

linux常见错误

1.E45: ‘readonly‘ option is set (add ! to override) 首先使用以下命令从Vim编辑器中出来&#xff1a;:qa!(强制退出) 接下来&#xff0c;使用sudo vim filename和更高版本&#xff1a;:wq 2.Bash script – "/bin/bash^M: bad interpreter: No such file or direc…

如何退回chrome旧版ui界面?关闭Chrome浏览器新 UI 界面

之前启用新UI的方式 Chrome 已经很久没有进行过大的样式修改&#xff0c;但近期在稳定分支中添加了新的 flags 实验性标志&#xff0c;带来了全新的设计与外观&#xff0c;启用方式如下&#xff1a; 在 Chrome 浏览器的搜索栏中输入并访问 chrome://flags 搜索“refresh 2023…

高效营销系统集成:百度营销的API无代码解决方案,提升电商与广告效率

百度营销API连接&#xff1a;构建无代码开发的高效集成体系 在数字营销的高速发展时代&#xff0c;企业追求的是快速响应市场的能力以及提高用户运营的效率。百度营销API连接正是为此而生&#xff0c;它通过无代码开发的方式&#xff0c;实现了电商平台、营销系统和CRM的一站式…

第十一章 SpringCloud Alibaba 实现Rocketmq–消息驱动

MQ简介 什么是MQ MQ&#xff08;Message Queue&#xff09;是一种跨进程的通信机制&#xff0c;用于传递消息。通俗点说&#xff0c;就是一个先进先出的数 据结构。 MQ的应用场景 异步解耦 最常见的一个场景是用户注册后&#xff0c;需要发送注册邮件和短信通知&#xff…

Qt中槽函数在那个线程执行的探索和思考

信号和槽是Qt的核心机制之一&#xff0c;通过该机制大大简化了开发者的开发难度。信号和槽属于观察者模式&#xff08;本质上是回调函数的应用&#xff09;。是函数就需要考虑其是在那个线程中执行&#xff0c;本文讨论的就是槽函数在那个线程中执行的问题。 目录 1. connect…

[BUG]TDA4 main域 CAN 无法进中断

目录 关键词平台说明一、背景二、根本原因2.1 Com模块 三、措施 关键词 嵌入式、C语言、autosar、TDA4 平台说明 项目ValueOSautosar OSautosar厂商vector芯片厂商TI编程语言C&#xff0c;C编译器HighTec (GCC) 一、背景 在将mcu域的部分can 移植到main域的时候发现无法进…

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《考虑灵活性资源传输精细化建模的配电网优化运行》

这个标题表达的是关于配电网优化运行的一个概念&#xff0c;其中考虑了灵活性资源传输的精细化建模。让我们逐个解读关键词&#xff1a; 考虑灵活性资源传输&#xff1a;这指的是在配电网优化运行中考虑到不同类型的灵活性资源的传输。灵活性资源包括可再生能源、储能系统、柔性…

HarmonyOS首次尝试-HelloWorld

我的旧手机是个HUAWEI PCT-AL10 HarmonyOS 3.0.0(Android 10) 插上后&#xff0c;studio能显示连接上了手机设备&#xff0c;创建的demo使用的是API9&#xff0c;也就是当前的最新版本。 点击运行报错&#xff1a; 点击去往帮助页&#xff0c;做的也挺好&#xff0c;有直达的…

抠图软件哪个好用?什么软件可以抠图换背景?

抠图软件哪个好用&#xff1f;在图片处理中&#xff0c;抠图换背景是一项常见的操作。很多新手可能会对此感到困惑&#xff0c;不知道应该使用什么软件来进行抠图换景。实际上&#xff0c;现在市面上有很多图片处理软件都具备抠图换背景的功能&#xff0c;每款软件都有其优缺点…

开辟“护眼绿洲”,荣耀何以为师?

文 | 智能相对论 作者 | 佘凯文 俗话说&#xff0c;眼睛是心灵的窗户&#xff0c;可如今&#xff0c;人们对于这扇“窗户”的保护&#xff0c;似乎越来越不重视。 据人民日报今年发布的调查显示&#xff0c;中国眼病患病人数2.1亿&#xff0c;近视患者人数多达6亿&#xff0…

Python学习之爬虫基础

目录 文章声明⭐⭐⭐让我们开始今天的学习吧&#xff01;requests库的基本使用BeautifulSoup解析HTML我们还需要学习什么呢&#xff1f; 文章声明⭐⭐⭐ 该文章为我&#xff08;有编程语言基础&#xff0c;非编程小白&#xff09;的 Python爬虫自学笔记知识来源为 B站UP主&…

【JVM从入门到实战】(五)类加载器

一、什么是类加载器 类加载器&#xff08;ClassLoader&#xff09;是Java虚拟机提供给应用程序去实现获取类和接口字节码数据的技术。 类加载器只参与加载过程中的字节码获取并加载到内存这一部分。 二、jdk8及之前的版本 类加载器分为三类&#xff1a; 启动类加载器-加载Ja…

2043杨辉三角(C语言)

目录 一&#xff1a;题目 二&#xff1a;思路分析 三&#xff1a;代码 一&#xff1a;题目 二&#xff1a;思路分析 1.通过杨辉三角&#xff0c;不难发现中间的数等于肩头两个数之和 2.但是当我们的输出结果&#xff0c;与杨辉三角的形式有所不同&#xff0c;但是我们可以找…

【Linux】高性能 Web 服务器 Nginx 安装教程(Ubuntu 22.04)

前言 Nginx 是一个高性能的开源 Web 服务器软件&#xff0c;也可以用作反向代理服务器、负载均衡器、HTTP 缓存以及作为邮件代理服务器等。Nginx 以其高性能、稳定性和丰富的功能而闻名&#xff0c;被广泛用于构建高流量网站和应用程序。 步骤 更新软件源 首先需要更新系统的软…

AttributeError: module ‘edge_tts‘ has no attribute ‘Communicate‘解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

pycdc配置和使用

配置 使用的kali2023版本 安装cmake pip install cmake 下载pycdc git clone https://github.com/zrax/pycdc 切换到pycdc目录 cd pycdc 进行cmake cmake CMakeLists.txt make 使用 显示帮助信息 ./pycdc -h 显示帮助信息 反编译 ./pycdc /home/kali/Desktop/main…

瑞萨单片机学习:RA4M3单片机 BOOTloader升级 跳转到主程序 主程序无法执行问题

背景&#xff1a; 使用瑞萨的RA4M3单片机编写BOOT引导程序进行测试&#xff0c;在BOOT程序跳转到主程序时&#xff0c;主程序无法执行。本文介绍了问题的定位和解决方法。 运行开发环境介绍 硬件环境 RA4M3 官方开发板 J-LINK V11 开发板自带 软件开发环境 e2 studio VSCODE…

【MySQL基础】MySQL基本操作详解

系列文章目录 第1篇&#xff1a;【MySQL基础】MySQL介绍及安装 第2篇&#xff1a;【MySQL基础】MySQL基本操作详解 文章目录 ✍1&#xff0c;数据库操作     &#x1f50d;1.1,查看数据库     &#x1f50d;1.2,创建数据库     &#x1f50d;1.3,选择数据库    …

探索太空深渊:计算机技术在航天领域的无限可能

探索太空深渊&#xff1a;计算机技术在航天领域的无限可能 一、引言 在21世纪的科技浪潮中&#xff0c;太空探索和计算机技术无疑是两个最为璀璨夺目的领域。它们各自的发展都足以改变人类社会的未来&#xff0c;而当这两者交汇时&#xff0c;所激发出的创新和变革更是超乎我…