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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...