当前位置: 首页 > 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…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...