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

Leetcode 剑指 Offer II 098.不同路径

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

一个机器人位于一个 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 * 10^9

题目思考

  1. 如何优化时间和空间复杂度?

解决方案

方法 1

  • 分析题目, 机器人只能向下或向右移动, 我们可以利用这一点, 累加当前坐标的左边和上边相邻坐标的路径数来得到当前坐标的路径数
  • 显然这就是动态规划的思路:
    • dp[r][c] 代表坐标(r,c)的路径数
    • 初始化 dp[0][0] = 1, 其他值全是 0, 表示开始时起点的路径数为 1
    • 然后进行状态转移: dp[r][c] = dp[r-1][c] + dp[r][c-1] (如果 r 或 c 为 0, 则相应的 r-1 或 c-1 的 dp 值就是 0, 只能从另一个方向转移而来)
    • 最终右下角坐标的 dp[m-1][n-1] 就代表总路径数
  • 下面的代码有详细的注释, 方便大家理解
复杂度
  • 时间复杂度 O(MN): 需要两重循环求 DP 值
  • 空间复杂度 O(MN): 二维 DP 数组的空间消耗
代码
class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0] * n for _ in range(m)]for r in range(m):for c in range(n):if (r, c) == (0, 0):# 起点dp值初始化为1dp[r][c] = 1else:# 左侧邻居路径数, 不存在时为0ldp = 0 if c == 0 else dp[r][c - 1]# 上侧邻居路径数, 不存在时为0udp = 0 if r == 0 else dp[r - 1][c]# 累加两个邻居的路径数dp[r][c] = ldp + udp# 最终结果就是右下角路径数return dp[m - 1][n - 1]

方法 2

  • 上面的 DP 做法固然可以解决这个问题, 那是否可以继续优化呢?
  • 答案是肯定的, 我们从另一个角度来思考这个问题, 机器人一共移动 m+n-2 次, 然后每次移动要么向下, 要么向右, 一共向下移动 m-1 次, 向右移动 n-1 次
  • 相当于从总移动次数 m+n-2 中选取 m-1 个, 我们可以利用数学求组合数的方法, 也即 C(m+n-2, m-1), 得到的值就是对应的总路径数
  • 这里可以额外进行一些优化, 使用 m 和 n 中的较小值来计算组合数, 对应的时间复杂度也是两者的较小值
  • 下面的代码有详细的注释, 方便大家理解
复杂度
  • 时间复杂度 O(min(M,N)): 求组合数时需要累乘 M-1 或 N-1 次, 取两者较小值
  • 空间复杂度 O(1): 没有使用额外变量
代码
class Solution:def uniquePaths(self, m: int, n: int) -> int:# 共有m+n-2次移动, 然后从中选择m-1次向下, 剩下n-1次向右# 所以总路径数就是组合数C(m+n-2,m-1) (也等于C(m+n-2,n-1))# 额外优化, 使用m和n的较小值来计算组合数mn = min(m, n)return math.comb(m + n - 2, mn - 1)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

相关文章:

Leetcode 剑指 Offer II 098.不同路径

题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下…...

LabVIEW智能螺杆空压机测试系统

基于LabVIEW软件开发的螺杆空压机测试系统利用虚拟仪器技术进行空压机的性能测试和监控。系统能够实现对螺杆空压机关键性能参数如压力、温度、流量、转速及功率的实时采集与分析&#xff0c;有效提高测试效率与准确性&#xff0c;同时减少人工操作&#xff0c;提升安全性。 项…...

在 Ubuntu 22.04 上安装 PHP 8.2

在 Ubuntu 22.04 上安装 PHP 8.2&#xff0c;可以按照以下步骤进行&#xff1a; 更新系统软件包&#xff1a; 首先&#xff0c;确保你的系统软件包是最新的。 sudo apt update sudo apt upgrade 安装 PHP PPA&#xff08;Personal Package Archive&#xff09;&#xff1a; U…...

Java生死簿管理小系统(简单实现)

学习总结 1、掌握 JAVA入门到进阶知识(持续写作中……&#xff09; 2、学会Oracle数据库入门到入土用法(创作中……&#xff09; 3、手把手教你开发炫酷的vbs脚本制作(完善中……&#xff09; 4、牛逼哄哄的 IDEA编程利器技巧(编写中……&#xff09; 5、面经吐血整理的 面试技…...

【VoceChat】一个即时聊天(IM)软件,又是一个可以嵌入任何网页聊天系统

为什么要搭建私人聊天软件 在当今数字化时代&#xff0c;聊天软件已经成为人们日常沟通和协作的重要工具。市面上的公共聊天平台虽然方便&#xff0c;但也伴随着诸多隐私、安全、广告和功能限制的问题。对于那些注重数据安全、追求高效沟通的个人或团队来说&#xff0c;搭建一…...

【LeetCode】动态规划—96. 不同的二叉搜索树(附完整Python/C++代码)

动态规划—96. 不同的二叉搜索树 题目描述前言基本思路1. 问题定义2. 理解问题和递推关系二叉搜索树的性质&#xff1a;核心思路&#xff1a;状态定义&#xff1a;状态转移方程&#xff1a;边界条件&#xff1a; 3. 解决方法动态规划方法&#xff1a;伪代码&#xff1a; 4. 进一…...

Nginx UI 一个可以管理Nginx的图形化界面工具

Nginx UI 是一个基于 Web 的图形界面管理工具&#xff0c;支持对 Nginx 的各项配置和状态进行直观的操作和监控。 Nginx UI 的功能非常丰富&#xff1a; 在线查看服务器 CPU、内存、系统负载、磁盘使用率等指标 在线 ChatGPT 助理 一键申请和自动续签 Let’s encrypt 证书 在…...

Vue向上滚动加载数据时防止内容闪动

目前的需求&#xff1a;当前组件向上滚动加载数据&#xff0c;dom加载完后&#xff0c;页面的元素位置不能发生变化 遇到的问题&#xff1a;加载完数据后&#xff0c;又把滚轮滚到之前记录的位置时&#xff0c;内容发生闪动 现在的方案&#xff1a; 加载数据之前记录整体滚动条…...

基于QT、ARM的智能停车管理系统+高分项目+源码

Parking-management-system 本系统基于QT、ARM开发板、Linux系统并对接百度AI 1.1 项目目的: 创建一个智能停车管理系统&#xff0c;能够停入车辆和取出车辆以及查询车辆停入停车场的状态并且计算车辆离开时收费情况。 1.2 项目意义: 实现停车场智能抬杆和智能收费系统&…...

1.6,unity动画Animator屏蔽某个部位,动画组合

动画组合 一边跑一边攻击 using System.Collections; using System.Collections.Generic; using UnityEngine;public class One : MonoBehaviour {private Animator anim;// Start is called before the first frame updatevoid Start(){anim GetComponent<Animator>();…...

发动机冷却系统排空气

发动机冷却系统排空气的几种常见方法 发动机冷却系统是汽车发动机的重要组成部分&#xff0c;它的主要作用是通过循环冷却液来吸收和散发发动机产生的热量&#xff0c;确保发动机在正常工作温度下运行。然而&#xff0c;在冷却系统的运行过程中&#xff0c;由于各种原因&#…...

三周精通FastAPI:1 第一步入门

FastAPI是一个非常棒的python web和api框架&#xff0c;准备用三周的时间“精通它” 学习流程参考FastAPI官网的用户教程&#xff1a;教程 - 用户指南 - FastAPI 学前提示 运行代码 所有代码片段都可以复制后直接使用&#xff08;它们实际上是经过测试的 Python 文件&#x…...

RestTemplate基本使用之HTTP实现GET请求和POST请求

一、GET请求实例 public static TianQi getTianQi(String city) {RestTemplate restTemplate new RestTemplate();HashMap res restTemplate.getForObject("http://www.tianqiapi.com/api/?versionv6&appid15118158&appsecretgVNnwva8&city" city, H…...

2024-10-18 问AI: [AI面试题] 神经网络有哪些不同类型?

文心一言 神经网络有多种不同类型&#xff0c;每种类型都有其特定的结构和应用场景。以下是一些主要的神经网络类型&#xff1a; 前馈神经网络&#xff08;FNN&#xff09;&#xff1a; 也称为全连接神经网络或感知器网络。由输入层、隐藏层和输出层组成&#xff0c;信息流是单…...

【开源免费】基于SpringBoot+Vue.JS课程作业管理系统(JAVA毕业设计)

本文项目编号 T 023 &#xff0c;文末自助获取源码 \color{red}{T023&#xff0c;文末自助获取源码} T023&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…...

jmeter中对于有中文内容的csv文件怎么保存

jmeter的功能很强大&#xff0c;但是细节处没把握好就得不到预期的结果。今天来讲讲有中文内容的csv文件的参数化使用中需要注意的事项。 对于有中文内容&#xff0c;涉及到编码格式&#xff0c;为了让jmeter能正确地读取csv文件中的中文&#xff0c;需要把文件转码为UTF-8BOM…...

Leetcode 921 Shortest Path in Binary Matrix

题意&#xff1a;求二维矩阵中往8个方向移动的话&#xff0c;从左上方到右下方移动的最短路径 https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 解答&#xff1a;bfs易得 class Solution { public:int shortestPathBinaryMatrix(vector<vecto…...

第二十二篇——菲欧几何:相对论的数学基础是什么?

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华 一、背景介绍 对于几何的几个工具&#xff0c;让我再次感叹数学的伟大&#xff0c;逻辑…...

【AI整合包及教程】EchoMimic:开创数字人新时代,让静态图像“活”起来!

在数字化浪潮的推动下&#xff0c;人工智能技术正以前所未有的速度渗透到我们生活的方方面面。从智能家居到自动驾驶&#xff0c;从智能客服到医疗诊断&#xff0c;AI的触角无处不在。而如今&#xff0c;阿里巴巴旗下的蚂蚁集团再次引领潮流&#xff0c;宣布开源其革命性的数字…...

ArcGIS 最新底图服务地址

ArcGIS 最新底图服务地址 说明 先上地址&#xff1a; 地形图&#xff1a; https://services.arcgisonline.com/arcgis/rest/services/Elevation/World_Hillshade/MapServer深色地形图&#xff1a;https://services.arcgisonline.com/arcgis/rest/services/Elevation/World_Hi…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

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

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

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...