【动态规划】路径问题_不同路径_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++
题目链接:leetcode不同路径 目录 题目解析: 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目解析: 题目让我们求总共有多少条不同的路径可到达右下角; 由题可得: 机器人位于…...
Python并发-线程和进程
一、线程和进程对应的问题 **1.进程:**CPU密集型也叫计算密集型,指的是系统的硬盘、内存性能相对CPU要好很多,此时,系统运作大部分的状况是CPU Loading 100%,CPU要读/写I/O(硬盘/内存),I/O在很短的时间就可…...
微信小程序适配方案:rpx(responsive pixel响应式像素单位)
小程序适配单位:rpx 规定任何屏幕下宽度为750rpx 小程序会根据屏幕的宽度自动计算rpx值的大小 Iphone6下:1rpx 1物理像素 0.5css 小程序编译后,rpx会做一次px换算,换算是以375个物理像素为基准,也就是在一个宽度…...
vue2 echarts饼状图,柱状图,折线图,简单封装以及使用
vue2 echarts饼状图,柱状图,折线图,简单封装以及使用 1. 直接上代码(复制可直接用,请根据自己的文件修改引用地址,图表只是简单封装,可根据自身功能,进行进一步配置。) …...
Linux信息收集
Linux信息收集 本机基本信息 #管理员 $普通用户 之前表示登录的用户名称,之后表示主机名,再之后表示当前所在目录 / 表示根目录 ~表示当前用户家目录1、内核,操作系统和设备信息 uname -a 打印所有可用的系统信息 uname -r 内核版本 u…...
三种定时任务总结
前言 springboot中设置定时任务有三种常见的方式,分别为: 基于Scheduled注解。基于Quartz框架。基于xxl-job框架。 下面将分别阐述下这三种方式的实现方式和优缺点。 1. Scheduled 介绍 Scheduled注解是Spring Framework提供的一个非常简单的创建定…...
[足式机器人]Part2 Dr. CAN学习笔记-数学基础Ch0-6复数Complex Number
本文仅供学习使用 本文参考: B站: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 代数表达: z a b i , R e ( z ) a , I m ( z ) b zabi,\mathrm{Re}…...
使用 MITRE ATTCK® 框架缓解网络安全威胁
什么是MITRE ATT&CK框架 MITRE Adversarial Tactics, Techniques, and Common Knowledge(ATT&CK)是一个威胁建模框架,用于对攻击者用来入侵企业、云和工业控制系统(ICS)并发起网络攻击…...
从零构建属于自己的GPT系列4:模型训练3(训练过程解读、序列填充函数、损失计算函数、评价函数、代码逐行解读)
🚩🚩🚩Hugging Face 实战系列 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在PyCharm中进行 本篇文章配套的代码资源已经上传 从零构建属于自己的GPT系列1:数据预处理 从零构建属于自己的GPT系列2:模型训…...
光学遥感显著目标检测初探笔记总结
目录 观看地址介绍什么是显著性目标检测根据不同的输入会有不同的变体(显著性目标检测家族)目前这个领域的挑战 技术方案论文1(2019)论文2(2021)论文3(2022) 未来展望 观看地址 b站链接 介绍 什么是显著性目标检测 一张图片里最吸引注意力的部分就是显著性物体,…...
HttpComponents: 领域对象的设计
1. HTTP协议 1.1 HTTP请求 HTTP请求由请求头、请求体两部分组成,请求头又分为请求行(request line)和普通的请求头组成。通过浏览器的开发者工具,我们能查看请求和响应的详情。 下面是一个HTTP请求发送的完整内容。 POST https://track.abc.com/v4/tr…...
使用wire重构商品微服务
一.wire简介 Wire 是一个轻巧的Golang依赖注入工具。它由Go Cloud团队开发,通过自动生成代码的方式在编译期完成依赖注入。 依赖注入是保持软件 “低耦合、易维护” 的重要设计准则之一。 此准则被广泛应用在各种开发平台之中,有很多与之相关的优秀工…...
大三上实训内容
项目一:爬取天气预报数据 【内容】 在中国天气网(http://www.weather.com.cn)中输入城市的名称,例如输入信阳,进入http://www.weather.com.cn/weather1d/101180601.shtml#input 的网页显示信阳的天气预报,其中101180601是信阳的…...
IOT安全学习路标
1. 物联网基础知识 首先,你需要建立坚实的物联网基础知识,包括IoT的架构和组件,传感器和设备的连接和通信技术,云端和边缘计算等。 2. 通信和网络安全 学习关于物联网通信和网络安全的基础知识,包括加密和认证技术、…...
java中线程的状态是如何转换的?
在 Java 中,线程有几种状态,主要包括 NEW(新建)、RUNNABLE(可运行)、BLOCKED(阻塞)、WAITING(等待)、TIMED_WAITING(计时等待)、和 TE…...
处理合并目录下的Excel文件数据并指定列去重
处理合并目录下的Excel文件数据并指定列去重 需求:读取指定目录下的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信息,通常这些log信息是一些可以读懂的字符串信息,这些信息一般用来记录节点的运行状态。 ROS有五种不同类型的log信息,分别为:logdebug、loginfo、logwarn、logerr、logfatal。 等级由低到高&…...
学习git后,真正在项目中如何使用?
文章目录 前言下载和安装Git克隆远程仓库PyCharm链接本地Git创建分支修改项目工程并提交到本地仓库推送到远程仓库小结 前言 网上学习git的教程,甚至还有很多可视化很好的git教程,入门git也不是什么难事。但我发现,当我真的要从网上克隆一个…...
Qt国际化翻译Linguist使用
QT的国际化是非常方便的,简单的说就是QT有自带的翻译工具把我们源代码中的字符串翻译成任何语言文件,再把这个语言文件加载到项目中就可以显示不同的语言。下面直接上手: 步骤一:打开pro文件,添加:TRANSLA…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
