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

【动态规划】LeetCode-62.不同路径

🎈算法那些事专栏说明:这是一个记录刷题日常的专栏,每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目,在这立下Flag🚩
🏠个人主页:Jammingpro
📕专栏链接:算法那些事
🎯每日学习一点点,技术累计看得见

题目

题目描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?

执行示例

示例 1:
输入:m = 3, n = 7
输出:28
在这里插入图片描述

示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1.向右 -> 向下 -> 向下
2.向下 -> 向下 -> 向右
3.向下 -> 向右 -> 向下

示例 3:
输入:m = 7, n = 3
输出:28

示例 4:
输入:m = 3, n = 3
输出:6

提示

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 1 0 9 10^9 109

题解

以示例1为例,因为机器人只能向右或向下移动,因而到达第0行和第0列各个方格的方法数均为1。而到达map[i][j]的方法数等于map[i-1][j]+map[i][j-1],即当前方格同一列的上一行方法数+当前方格同一行的前一列方法数加和。因为可以从上面一个方格向下走1步到达当前方格,也可以从左侧方格走1步到达当前方格。如下图所示,通过不断执行map[i][j]=map[i-1][j]+map[i][j-1],最终map[m-1][n-1]中将保存到达右下角方格的方法数。
在这里插入图片描述
从而我们可以得到如下代码↓↓↓

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>map(m,vector<int>(n));//将第0行初始化为1for(int i = 0; i < n; i++){map[0][i] = 1;}//将第0列初始化为1for(int i = 0; i < m; i++){map[i][0] = 1;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){map[i][j]=map[i-1][j]+map[i][j-1];}}return map[m-1][n-1];}
};

这里我们使用了两次循环去初始化第0行和第0列,我们可以通过多开辟一行一列,并将map[0][1]初始化为1,这时,我们就不再需要初始化第1行第1列。而我们的结果保存在map[m][n]。
ps:这个方法很巧妙,就是不大好描述。大家看一下下方代码,大脑运行一下。↓↓↓

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>map(m + 1, vector<int>(n + 1));map[0][1] = 1;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)map[i][j] = map[i - 1][j] + map[i][j - 1];return map[m][n];}
};

本文存在不足,欢迎留言或私信批评、指正。希望我的解决方法能够对你有所帮助~~
今日打卡完成,点亮小星星☆→★

相关文章:

【动态规划】LeetCode-62.不同路径

&#x1f388;算法那些事专栏说明&#xff1a;这是一个记录刷题日常的专栏&#xff0c;每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目&#xff0c;在这立下Flag&#x1f6a9; &#x1f3e0;个人主页&#xff1a;Jammingpro &#x1f4d5;专栏链接&…...

对 Vision Transformers 及其基于 CNN-Transformer 的变体的综述

A survey of the Vision Transformers and its CNN-Transformer based Variants 摘要1、介绍2、vit的基本概念2.1 patch嵌入2.2 位置嵌入2.2.1 绝对位置嵌入(APE)2.2.2 相对位置嵌入(RPE)2.2.3卷积位置嵌入(CPE) 2.3 注意力机制2.3.1多头自我注意(MSA) 2.4 Transformer层2.4.1 …...

MongoDB简介

数据库&#xff0c;顾名思义&#xff0c;是保存数据的地方。中华文化博大精深&#xff0c;短短3个文字&#xff0c;就定义了一个强大的数据管理和读写方式出来。数据库&#xff0c;管理的对象是数据。称为库&#xff0c;表示数据在库中有组织&#xff0c;相互之间有微妙的关系。…...

尚硅谷hadoop3.x课程部分资料文件下载,jdk,hadoopjar包

jdk文件百度云下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1MCiGRzOZY8rAFpRJwA3tdw 提取码&#xff1a;kphl hadoop的jar包&#xff1a; 最新版官网链接&#xff1a; Index of /dist/hadoop/core/stable (apache.org) 百度云下载&#xff0c;3.3.3版&#xf…...

vue el-radio-group多选封装及使用

基于Element UI库的Vue组件&#xff0c;实现了一个单选/多选框组合的效果&#xff0c;可以根据 type 属性的不同值来切换单选框&#xff08;默认&#xff09;和按钮式单选框/多选框。 创建组件index.vue (src/common-ui/radioGroup/index.vue) <template><el-radio-g…...

Kaggle-水果图像分类银奖项目 pytorch Densenet GoogleNet ResNet101 VGG19

一些原理文章 卷积神经网络基础&#xff08;卷积&#xff0c;池化&#xff0c;激活&#xff0c;全连接&#xff09; - 知乎 PyTorch 入门与实践&#xff08;六&#xff09;卷积神经网络进阶&#xff08;DenseNet&#xff09;_pytorch conv1x1_Skr.B的博客-CSDN博客GoogLeNet网…...

TPLink-Wr702N 通过OpenWrt系统打造打印服务器实现无线打印

最近淘到了一个TPLink-Wr702N路由器&#xff0c;而且里面已经刷机为OpenWrt系统了&#xff0c;刚好家里有一台老的USB打印机&#xff0c;就想这通过路由器将打印机改为无线打印机&#xff0c;一番折腾后&#xff0c;居然成功了&#xff0c;这里记录下实现过程&#xff0c;为后面…...

[UGUI]实现从一个道具栏拖拽一个UI道具到另一个道具栏

在Unity游戏开发中&#xff0c;实现UI道具的拖拽功能是一项常见的需求。本文将详细介绍如何使用Unity的UGUI系统和事件系统&#xff0c;实现从一个道具栏拖拽一个UI道具到另一个道具栏的功能。 一、准备工作 首先&#xff0c;你需要在Unity中创建两个道具栏和一些UI道具。道具…...

微服务--08--Seata XA模式 AT模式

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 分布式事务Seata 1.XA模式1.1.两阶段提交1.2.Seata的XA模型1.3.优缺点 AT模式2.1.Seata的AT模型2.2.流程梳理2.3.AT与XA的区别 分布式事务 > 事务–01—CAP理论…...

Doris 数据导入一:Broker Load 方式

1.Doris导入数据的方式总结 导入(Load)功能就是将用户的原始数据导入到 Doris 中。导入成功后,用户即可通过 Mysql 客户端查询数据。为适配不同的数据导入需求,Doris 系统提供了6种不同的导入方式。每种导入方式支持不同的数据源,存在不同的使用方式(异步,同步)。 所有…...

docker踩坑记录:docker容器创建doris容器间无法通讯问题

背景&#xff1a; 开发大数据平台&#xff0c;使用doris作为数据仓储&#xff0c;使用docker做集群部署&#xff0c;先进行开发环境搭建&#xff0c;环境为BE1;FE1&#xff0c;原来使用官方例子&#xff0c;但是官方例子是创建了一个bridge使用172.20.80.0/24通讯&#xff0c;…...

springboot+java校园自助洗衣机预约系统的分析与设计ssm+jsp

洗衣服是每个人都必须做的事情&#xff0c;而洗衣机更成为了人们常见的电器&#xff0c;但是单个洗衣机价格不菲&#xff0c;如果每人都买&#xff0c;就会造成资源的冗余。所有就出现了公用设备&#xff0c;随着时代的发展&#xff0c;很多公用都开始向着无人看守的自助模式经…...

TCP简介及特性

1. TCP协议简介 TCP是Transmission Control Protocol的简称&#xff0c;中文名是传输控制协议。它是一种面向连接的、可靠的、基于IP的传输层协议。两个TCP应用之间在传输数据的之前必须建立一个TCP连接&#xff0c;TCP采用数据流的形式在网络中传输数据。TCP为了保证报文传输的…...

ElasticSearch 排障常用方法

文章目录 1&#xff0c;集群状态&#xff0c;节点在线情况&#xff0c;集群参数配置2&#xff0c;查看异常索引、分片&#xff0c;分析异常原因&#xff0c;手动分配分片 1&#xff0c;集群状态&#xff0c;节点在线情况&#xff0c;集群参数配置 GET _cluster/health?pretty…...

【SA8295P 源码分析 (四)】136 - QNX 如何抓取系统 log 方法 之 网络部分日志抓取方法

【SA8295P 源码分析】136 - QNX 如何抓取系统 log 方法 之 网络部分日志抓取方法 一、slog2info二、获取当前系统网络信息三、tracelogger四、qscan.sh : 用于收集 qnx 文件系统 权限、checksums 等信息系列文章汇总见:《【SA8295P 源码分析 (四)】网络模块 文章链接汇总 - 持…...

传统算法:使用Pygame实现SVM(支持向量机)算法

使用 Pygame 演示了支持向量机(SVM)在二维数据上的分类过程。以下是代码的主要步骤和原理解释: 1、初始化和基本设置 Pygame 初始化: 通过 pygame.init() 初始化 Pygame。 定义颜色和屏幕大小: 定义了一些颜色常量(WHITE, BLACK, RED, BLUE)和屏幕的宽度和高度。 创建…...

cookie wzws_sess** 逆向

声明 本文章中所有内容仅供学习交流&#xff0c;抓包内容、敏感网址、数据接口均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff0c;若有侵权&#xff0c;请联系我立即删除&#xff01; 网站&#xff1a; aHR0…...

JIRA 基本使用

该页面可以&#xff1a; 查看个人基本信息以及归属的邮件组修改常用参数配置查看指给自己的 Open 问题查看自己最近的活动记录等 权限管理 Project 权限管理 JIRA 项目有三种通用权限方案&#xff1a; 公开权限方案&#xff08;默认禁止使用此方案&#xff09;&#xff1a…...

什么是JVM的内存模型?详细阐述Java中局部变量、常量、类名等信息在JVM中的存储位置

导航&#xff1a; 【Java笔记踩坑汇总】Java基础JavaWebSSMSpringBootSpringCloud瑞吉外卖/黑马旅游/谷粒商城/学成在线设计模式面试题汇总性能调优/架构设计源码-CSDN博客 目录 一、JVM基本介绍 二、JVM内存模型 2.0 概述 2.1 类加载子系统 2.2 运行时数据区 2.2.0 基本…...

c#学习相关系列之as和is的相关用法

一、子类和父类的关系 public class Program{static void Main(string[] args){Animal animal new Dog();// Dog dog (Dog)new Animal(); 编译成功&#xff0c;运行报错Dog dog (Dog)animal;Dog dog new Dog();Animal animal dog; //等价于Animal animal new Dog();}}pub…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...