当前位置: 首页 > news >正文

【动态规划】路径问题_不同路径_C++

题目链接:leetcode不同路径


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求总共有多少条不同的路径可到达右下角;

由题可得:

机器人位于一个 m x n 网格;

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

我们拿示例2来分析:

则根据题目要求我们只能向下或者向右移动一步,不能向上或向左回退;

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


算法原理:

1.状态表示

根据题目要求,先创建一个 m x n 大小的dp表

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

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

这种状态表示怎么来的?

1.经验+题目要求

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

题目让我们求到达右下角有多少种方式,那么这里我们可以dp[i][j]来表示。

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

2.状态转移方程

dp[i][j]等于什么?

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

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

当机器人到达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];

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

相关文章:

【动态规划】路径问题_不同路径_C++

题目链接&#xff1a;leetcode不同路径 目录 题目解析&#xff1a; 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目解析&#xff1a; 题目让我们求总共有多少条不同的路径可到达右下角&#xff1b; 由题可得&#xff1a; 机器人位于…...

Python并发-线程和进程

一、线程和进程对应的问题 **1.进程&#xff1a;**CPU密集型也叫计算密集型&#xff0c;指的是系统的硬盘、内存性能相对CPU要好很多&#xff0c;此时&#xff0c;系统运作大部分的状况是CPU Loading 100%&#xff0c;CPU要读/写I/O(硬盘/内存)&#xff0c;I/O在很短的时间就可…...

微信小程序适配方案:rpx(responsive pixel响应式像素单位)

小程序适配单位&#xff1a;rpx 规定任何屏幕下宽度为750rpx 小程序会根据屏幕的宽度自动计算rpx值的大小 Iphone6下&#xff1a;1rpx 1物理像素 0.5css 小程序编译后&#xff0c;rpx会做一次px换算&#xff0c;换算是以375个物理像素为基准&#xff0c;也就是在一个宽度…...

vue2 echarts饼状图,柱状图,折线图,简单封装以及使用

vue2 echarts饼状图&#xff0c;柱状图&#xff0c;折线图&#xff0c;简单封装以及使用 1. 直接上代码&#xff08;复制可直接用&#xff0c;请根据自己的文件修改引用地址&#xff0c;图表只是简单封装&#xff0c;可根据自身功能&#xff0c;进行进一步配置。&#xff09; …...

Linux信息收集

Linux信息收集 本机基本信息 #管理员 $普通用户 之前表示登录的用户名称&#xff0c;之后表示主机名&#xff0c;再之后表示当前所在目录 / 表示根目录 ~表示当前用户家目录1、内核&#xff0c;操作系统和设备信息 uname -a 打印所有可用的系统信息 uname -r 内核版本 u…...

三种定时任务总结

前言 springboot中设置定时任务有三种常见的方式&#xff0c;分别为&#xff1a; 基于Scheduled注解。基于Quartz框架。基于xxl-job框架。 下面将分别阐述下这三种方式的实现方式和优缺点。 1. Scheduled 介绍 Scheduled注解是Spring Framework提供的一个非常简单的创建定…...

[足式机器人]Part2 Dr. CAN学习笔记-数学基础Ch0-6复数Complex Number

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记-数学基础Ch0-6复数Complex Number x 2 − 2 x 2 0 ⇒ x 1 i x^2-2x20\Rightarrow x1\pm i x2−2x20⇒x1i 代数表达&#xff1a; z a b i , R e ( z ) a , I m ( z ) b zabi,\mathrm{Re}…...

使用 MITRE ATTCK® 框架缓解网络安全威胁

什么是MITRE ATT&CK框架 MITRE Adversarial Tactics&#xff0c; Techniques&#xff0c; and Common Knowledge&#xff08;ATT&CK&#xff09;是一个威胁建模框架&#xff0c;用于对攻击者用来入侵企业、云和工业控制系统&#xff08;ICS&#xff09;并发起网络攻击…...

从零构建属于自己的GPT系列4:模型训练3(训练过程解读、序列填充函数、损失计算函数、评价函数、代码逐行解读)

&#x1f6a9;&#x1f6a9;&#x1f6a9;Hugging Face 实战系列 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在PyCharm中进行 本篇文章配套的代码资源已经上传 从零构建属于自己的GPT系列1&#xff1a;数据预处理 从零构建属于自己的GPT系列2&#xff1a;模型训…...

光学遥感显著目标检测初探笔记总结

目录 观看地址介绍什么是显著性目标检测根据不同的输入会有不同的变体(显著性目标检测家族)目前这个领域的挑战 技术方案论文1(2019)论文2(2021)论文3(2022) 未来展望 观看地址 b站链接 介绍 什么是显著性目标检测 一张图片里最吸引注意力的部分就是显著性物体&#xff0c;…...

HttpComponents: 领域对象的设计

1. HTTP协议 1.1 HTTP请求 HTTP请求由请求头、请求体两部分组成&#xff0c;请求头又分为请求行(request line)和普通的请求头组成。通过浏览器的开发者工具&#xff0c;我们能查看请求和响应的详情。 下面是一个HTTP请求发送的完整内容。 POST https://track.abc.com/v4/tr…...

使用wire重构商品微服务

一.wire简介 Wire 是一个轻巧的Golang依赖注入工具。它由Go Cloud团队开发&#xff0c;通过自动生成代码的方式在编译期完成依赖注入。 依赖注入是保持软件 “低耦合、易维护” 的重要设计准则之一。 此准则被广泛应用在各种开发平台之中&#xff0c;有很多与之相关的优秀工…...

大三上实训内容

项目一&#xff1a;爬取天气预报数据 【内容】 在中国天气网(http://www.weather.com.cn)中输入城市的名称&#xff0c;例如输入信阳&#xff0c;进入http://www.weather.com.cn/weather1d/101180601.shtml#input 的网页显示信阳的天气预报&#xff0c;其中101180601是信阳的…...

IOT安全学习路标

1. 物联网基础知识 首先&#xff0c;你需要建立坚实的物联网基础知识&#xff0c;包括IoT的架构和组件&#xff0c;传感器和设备的连接和通信技术&#xff0c;云端和边缘计算等。 2. 通信和网络安全 学习关于物联网通信和网络安全的基础知识&#xff0c;包括加密和认证技术、…...

java中线程的状态是如何转换的?

在 Java 中&#xff0c;线程有几种状态&#xff0c;主要包括 NEW&#xff08;新建&#xff09;、RUNNABLE&#xff08;可运行&#xff09;、BLOCKED&#xff08;阻塞&#xff09;、WAITING&#xff08;等待&#xff09;、TIMED_WAITING&#xff08;计时等待&#xff09;、和 TE…...

处理合并目录下的Excel文件数据并指定列去重

处理合并目录下的Excel文件数据并指定列去重 需求&#xff1a;读取指定目录下的Excel文件并给数据做合并与去重处理 Python代码实现 import os import pandas as pd import warnings import time from tqdm import tqdm #进度条展示def read_excel(path):dfs []for file in…...

Numpy数组的去重 np.unique()(第15讲)

Numpy数组的去重 np.unique()(第15讲)         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ�…...

ROS-log功能区别

ROS使用rosout包来记录各个节点的log信息&#xff0c;通常这些log信息是一些可以读懂的字符串信息&#xff0c;这些信息一般用来记录节点的运行状态。 ROS有五种不同类型的log信息&#xff0c;分别为&#xff1a;logdebug、loginfo、logwarn、logerr、logfatal。 等级由低到高&…...

学习git后,真正在项目中如何使用?

文章目录 前言下载和安装Git克隆远程仓库PyCharm链接本地Git创建分支修改项目工程并提交到本地仓库推送到远程仓库小结 前言 网上学习git的教程&#xff0c;甚至还有很多可视化很好的git教程&#xff0c;入门git也不是什么难事。但我发现&#xff0c;当我真的要从网上克隆一个…...

Qt国际化翻译Linguist使用

QT的国际化是非常方便的&#xff0c;简单的说就是QT有自带的翻译工具把我们源代码中的字符串翻译成任何语言文件&#xff0c;再把这个语言文件加载到项目中就可以显示不同的语言。下面直接上手&#xff1a; 步骤一&#xff1a;打开pro文件&#xff0c;添加&#xff1a;TRANSLA…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...