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

【LeetCode】62. 不同路径

1 问题

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

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

示例 2:

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

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

2 答案

这题直接不会

官方解

  1. 排列组合,机器到底右下角,向下几步,向右几步都是固定的。
class Solution:def uniquePaths(self, m: int, n: int) -> int:return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))  # math.factorial(m+n-2) 为 m+n-2 的阶乘
  1. 动态规划
    dp[i][j] 是到达 i, j 最多路径
    则动态规划转移方程:dp[i][j] = dp[i-1][j] + dp[i][j-1](左边一格的最多路径+上面一格的最多路径)
class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[-1][-1]

优化,动态规划转移方程:dp[i]+=dp[i-1]

class Solution:def uniquePaths(self, m: int, n: int) -> int:cur = [1] * n  # 代表第一行for i in range(1, m):for j in range(1, n):cur[j] += cur[j-1]  # 代表这个位置上一行的数据,又上一行到这行只有一种路径,因此只需要再加上左侧右移的路径便可以return cur[-1]

相关文章:

【LeetCode】62. 不同路径

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

【lesson13】进程地址空间收尾

文章目录 进程地址空间存在的原因原因一原因二原因三 重新理解什么是挂起? 进程地址空间存在的原因 原因一 凡是非法访问或者映射,OS都会识别到,并终止该进程。 例子: 我们会发现我们定义的字符串常量只有只读权限,…...

Microsoft Edge中使用开源的ChatGPT

一、双击打开浏览器 找到:扩展,打开 二、打开Microsoft Edge加载项 三、Move tab新标签 获取免费ChatGPT 四、启用Move tab。启用ChatGPT。 扩展 管理扩展 启用 五、新建标签页,使用GPT 六、使用举例 提问 GPT回复...

【C语言精髓之指针】结构体指针(->与.两个运算符的区别)

/*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 通信与信息专业大二在读 * copyright 2023.10* COPYRIGHT 原创技术笔记:转载需获得博主本人同意,且需标明转载源* language C/C* IDE Base on Mic…...

SpringCloud 微服务全栈体系(一)

第一章 认识微服务 随着互联网行业的发展,对服务的要求也越来越高,服务架构也从单体架构逐渐演变为现在流行的微服务架构。这些架构之间有怎样的差别呢? 一、单体架构 单体架构:将业务的所有功能集中在一个项目中开发&#xff…...

Echarts自定义柱状图

目录 效果图 echarts官网找相似图 将柱状图引入html页面中 自定义柱状图 将不需要的属性删除 ​编辑 修改图形大小 grid 不显示x轴 ​编辑 不显示y轴线和相关刻度 ​编辑 y轴文字的颜色设置为自己想要的颜色 修改第一组柱子相关样式(条状) …...

LuatOS-SOC接口文档(air780E)-- ioqueue - io序列操作

ioqueue.init(hwtimer_id,cmd_cnt,repeat_cnt) 初始化一个io操作队列 参数 传入值类型 解释 int 硬件定时器id,默认用0,根据实际MCU确定,air105为0~5,与pwm共用,同一个通道号不能同时为pwm和ioqueue int 一个完…...

探讨Socks5代理技术的原理及其在不同领域的应用

Socks5代理:实现网络连接的智能之选 作为一种网络代理协议,Socks5代理技术通过转发网络数据包,实现了客户端和服务器之间的代理传输。其独特的特性在跨界电商、爬虫数据分析、企业出海和游戏体验等领域发挥着关键作用,为用户提供…...

sql注入的基本手法

目的 通过sqk注入获取数据内容 掌握sql注入基本手法 我们这里使用 1.联合注入 就是利用union select 语句 两条语句 同时执行 实现跨库跨表查询 条件 两条select语句查询结果具有相同列数 对应列数数据类型相同 简单的步骤 1.目标分析 ?id…...

8.1 C++ 标准输入输出流

C/C语言是一种通用的编程语言,具有高效、灵活和可移植等特点。C语言主要用于系统编程,如操作系统、编译器、数据库等;C语言是C语言的扩展,增加了面向对象编程的特性,适用于大型软件系统、图形用户界面、嵌入式系统等。…...

hive往es映射表写数据报错

hive是基于Hadoop的一个数据仓库工具,用来进行数据提取、转化、加载,这是一种可以存储、查询和分析存储在Hadoop中的大规模数据的机制。hive数据仓库工具能将结构化的数据文件映射为一张数据库表,并提供SQL查询功能,能将SQL语句转…...

2023年【广东省安全员A证第四批(主要负责人)】考试试卷及广东省安全员A证第四批(主要负责人)模拟考试

题库来源:安全生产模拟考试一点通公众号小程序 广东省安全员A证第四批(主要负责人)考试试卷根据新广东省安全员A证第四批(主要负责人)考试大纲要求,安全生产模拟考试一点通将广东省安全员A证第四批&#x…...

YOLOv5算法改进(15)— 如何去更换Neck网络(包括代码+添加步骤+网络结构图)

前言:Hello大家好,我是小哥谈。在学习完了如何去更换主干网络之后,接着就让我们通过案例的方式去学习下如何去更换Neck网络。本篇文章的特色就是比较浅显易懂,附加了很多的网络结构图,通过结构图的形式向大家娓娓道来,希望大家学习之后能够有所收获!🌈 前期回顾: YO…...

用Nginx搭建一个具备缓存功能的反向代理服务

在同一台服务器上,使用nginx提供服务,然后使用openresty提供反向代理服务。 参考《Ubuntu 20.04使用源码安装nginx 1.14.0》安装nginx。 参考《用Nginx搭建一个可用的静态资源Web服务器》搭建静态资源Web服务器,但是/nginx/conf/nginx.conf里…...

YOLOv5改进实战 | 更换主干网络Backbone(三)之轻量化模型Shufflenetv2

前言 轻量化网络设计是一种针对移动设备等资源受限环境的深度学习模型设计方法。下面是一些常见的轻量化网络设计方法: 网络剪枝:移除神经网络中冗余的连接和参数,以达到模型压缩和加速的目的。分组卷积:将卷积操作分解为若干个较小的卷积操作,并将它们分别作用于输入的不…...

【Markdown】 Markdown 操作备忘录

To Do List 显示目前todo list 的状态 getLogger() 单例类, 通过引入模块,获取单例日志对象 结果可视化调研 模型结果保存及测试 - [ ] getLogger() 单例类, 通过引入模块,获取单例日志对象 - [ ] 结果可视化调研 - [x] 模型结果…...

【自动化测试】基于Selenium + Python的web自动化框架

一、什么是Selenium? Selenium是一个基于浏览器的自动化工具,她提供了一种跨平台、跨浏览器的端到端的web自动化解决方案。Selenium主要包括三部分:Selenium IDE、Selenium WebDriver 和Selenium Grid:  1、Selenium IDE&…...

zookeeper连接客户端操作数据时报错Socket is not connected

文章目录 一、报错信息二、问题描述三、原因分析:四、解决方案: 一、报错信息 DEBUG org.apache.zookeeper.ClientCnxnSocketNIO - Ignoring exception during shutdown input java.net.SocketException: Socket is not connectedat sun.nio.ch.Net.tra…...

mysql select语句中from 之后跟查询语句

概念:将from后面的查询语句放在FROM的后面,则查询到的结果,就会被当成一个“表”; 这里有一个特别要注意的地方,放在FROM后面的子查询,必须要加别名。 select dui.id,dui.party_service_id mes_id, dui.party_id,dui.…...

Yolov8小目标检测(26):多尺度空洞注意力(MSDA) | 中科院一区顶刊 DilateFormer 2023.9

💡💡💡本文独家改进:多尺度空洞注意力(MSDA)采用多头的设计,在不同的头部使用不同的空洞率执行滑动窗口膨胀注意力(SWDA),全网独家首发,创新力度十足,适合科研 多尺度空洞注意力(MSDA) | 亲测在红外弱小目标检测涨点,map@0.5 从0.755提升至0.784 💡�…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...