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

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...