[特殊字符] LeetCode 62. 不同路径 | 动态规划+递归优化详解
在解 LeetCode 的过程中,路径计数问题是动态规划中一个经典的例子。今天我来分享一道非常基础但极具代表性的题目——不同路径。不仅适合初学者入门 DP(动态规划),还能帮助你打下递归思维的基础。
本文将介绍:
- 🔍 问题描述
- 💡 解题思路(包括递归+记忆化搜索)
- 🏆 代码实现与优化
- 📊 时间复杂度 & 空间复杂度分析
- 🔥 进阶思考
🔍 问题描述
一个机器人位于一个 m x n 的网格左上角(起点 Start)。
机器人每次只能向 右 或 下 移动一步,试图到达网格的右下角(终点 Finish)。
请问从起点到终点总共有多少条不同的路径?
✅ 示例
示例 1:
输入: m = 3, n = 7
输出: 28
示例 2:
输入: m = 3, n = 2
输出: 3
解释:
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3:
输入: m = 7, n = 3
输出: 28
示例 4:
输入: m = 3, n = 3
输出: 6
💡 解题思路
1️⃣ 递归 + 记忆化搜索(自顶向下)
我们可以把每一步的选择抽象成一个状态转移问题:
- 如果机器人在
(i, j)位置,它可以从 上面(i-1, j)或 左边(i, j-1)走过来。 - 到达
(i, j)的总路径数等于从(i-1, j)和(i, j-1)走过来的路径数之和。
状态转移方程:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件:
- 第一行和第一列上的每个位置的路径数都是
1(因为只能往一个方向走)。
为什么需要记忆化?
如果不加记忆化,递归会重复计算相同子问题,时间复杂度会指数级上升。通过记忆化存储已经计算过的结果,避免重复计算,大大降低了复杂度。
🏆 代码实现(Java)
class Solution {public int uniquePaths(int m, int n) {// 创建一个记忆数组,存储子问题的解int[][] memo = new int[m][n];return dfs(m - 1, n - 1, memo);}// 递归搜索函数,i 表示行数,j 表示列数private int dfs(int i, int j, int[][] memo) {// 边界情况,越界直接返回 0if (i < 0 || j < 0) {return 0;}// 如果到达起点 (0,0),只有 1 条路径if (i == 0 && j == 0) {return 1;}// 如果该位置已经计算过,直接返回记忆值if (memo[i][j] != 0) {return memo[i][j];}// 从上面和左边的路径数之和return memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);}
}
📊 时间复杂度 & 空间复杂度分析
-
时间复杂度:
O(m * n)
每个位置只会被访问一次,避免了重复计算。 -
空间复杂度:
O(m * n)
使用了一个二维数组来保存子问题的解。
🔥 进阶思考:动态规划(自底向上)
除了递归+记忆化,还可以使用**动态规划(DP)**的方式自底向上求解,避免了递归的栈消耗。
代码实现(DP):
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];// 初始化边界条件for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 1;// 状态转移方程填表for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
}
时间复杂度: O(m * n)
空间复杂度: O(m * n)(可以优化到 O(n),只用一维数组)
📚 其他进阶解法(组合数学)
如果你喜欢数学,可以用组合数的公式来解这道题:
- 一共需要移动
m-1步向下,n-1步向右。 - 总共
m+n-2步,从中选择m-1步向下。
公式:
C(m+n−2,m−1)=(m+n−2)!(m−1)!⋅(n−1)!C(m + n - 2, m - 1) = \frac{(m + n - 2)!}{(m - 1)! \cdot (n - 1)!}
Java 实现:
class Solution {public int uniquePaths(int m, int n) {long res = 1;for (int i = 1; i <= m - 1; i++) {res = res * (n - 1 + i) / i;}return (int) res;}
}
时间复杂度: O(min(m, n))
空间复杂度: O(1)
🎯 总结
- 🚀 使用 递归+记忆化搜索 解决子问题,避免重复计算。
- 🏆 使用 动态规划 解决自底向上的问题,避免递归栈溢出。
- ✨ 组合数学 提供最优解法,时间复杂度低,适合大规模输入。
如果你觉得这篇文章对你有帮助,别忘了点赞👍、收藏⭐和关注👀!欢迎在评论区和我交流更多动态规划的问题!
📢 更多 LeetCode 动态规划题解,敬请期待!
相关文章:
[特殊字符] LeetCode 62. 不同路径 | 动态规划+递归优化详解
在解 LeetCode 的过程中,路径计数问题是动态规划中一个经典的例子。今天我来分享一道非常基础但极具代表性的题目——不同路径。不仅适合初学者入门 DP(动态规划),还能帮助你打下递归思维的基础。 本文将介绍: &…...
常用的 JVM 参数:配置与优化指南
文章目录 常用的 JVM 参数:配置与优化指南引言 1. 内存管理参数1.1 堆内存配置1.2 方法区(元空间)配置1.3 直接内存配置 2. 垃圾回收参数2.1 垃圾回收器选择2.2 GC 日志配置2.3 GC 调优参数 3. 性能监控参数3.1 堆内存转储3.2 JVM 监控3.3 远…...
【JavaWeb学习Day17】
Tlias智能学习系统(员工管理) 新增员工: 三层架构职责: Controller:1.接收请求参数(员工信息);2.调用service方法;3.响应结果。 具体实现: /***新增员工…...
DeepSeek 提示词:定义、作用、分类与设计原则
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编…...
前端大文件上传
1. 开场概述 “大文件上传是前端开发中常见的需求,但由于文件体积较大,直接上传可能会遇到网络不稳定、服务器限制等问题。因此,通常需要采用分片上传、断点续传、并发控制等技术来优化上传体验” 2. 核心实现方案 “我通常会采用以下方案…...
JDK源码系列(一)Object
Object 概述 Object类是所有类的基类——java.lang.Object。 Object类是所有类的基类,当一个类没有直接继承某个类时,默认继承Object类Object类属于java.lang包下,此包下的所有类在使用时无需手动导入,系统会在程序编译期间自动…...
【Python 打造高效文件分类工具】
【Python】 打造高效文件分类工具 一、代码整体结构二、关键代码解析(一)初始化部分(二)界面创建部分(三)核心功能部分(四)其他辅助功能部分 三、运行与使用四、示图五、作者有话说 …...
大数据组件(四)快速入门实时数据湖存储系统Apache Paimon(1)
Paimon的下载及安装,并且了解了主键表的引擎以及changelog-producer的含义参考: 大数据组件(四)快速入门实时数据湖存储系统Apache Paimon(1) 利用Paimon表做lookup join,集成mysql cdc等参考: 大数据组件(四)快速入门实时数据…...
边缘安全加速(Edge Security Acceleration)
边缘安全加速(Edge Security Acceleration,简称ESA)是一种通过将安全功能与网络边缘紧密结合来提升安全性和加速网络流量的技术。ESA的目标是将安全措施部署到接近用户或设备的地方,通常是在网络的边缘,而不是将所有流…...
C/C++高性能Web开发框架全解析:2025技术选型指南
一、工业级框架深度解析(附性能实测) 1. Drogon v2.1:异步框架性能王者 核心架构: Reactor 非阻塞I/O线程池(参考Nginx模型) 协程实现:基于Boost.Coroutine2(兼容C11)…...
fedora 安装 ffmpeg 过程记录
参考博客:1. linux(centos)安装 ffmpeg,并添加 libx264库:https://blog.csdn.net/u013015301/article/details/140778199ffmpeg 执行时如添加参数 -vcodec libx264,会出现错误:Unknown encoder libx264’的错误,缺少li…...
【GPU驱动】OpenGLES图形管线渲染机制
OpenGLES图形管线渲染机制 OpenGL/ES 的渲染管线也是一个典型的图形流水线(Graphics Pipeline),包括多个阶段,每个阶段都负责对图形数据进行处理。管线的核心目标是将图形数据转换为最终的图像,这些图像可以显示在屏幕…...
Spring Boot项目@Cacheable注解的使用
Cacheable 是 Spring 框架中用于缓存的注解之一,它可以帮助你轻松地将方法的结果缓存起来,从而提高应用的性能。下面详细介绍如何使用 Cacheable 注解以及相关的配置和注意事项。 1. 基本用法 1.1 添加依赖 首先,确保你的项目中包含了 Spr…...
mac开发环境配置笔记
1. 终端配置 参考: Mac终端配置笔记-CSDN博客 2. 下载JDK 到 oracle官网 下载jdk: oracle官网 :Java Downloads | Oraclemac的芯片为Intel系列下载 x64版本的jdk;为Apple Mx系列使用 Arm64版本;oracle官网下载时报错:400 Bad R…...
重装CentOS YUM
1. 检查是否已安装 YUM 运行以下命令检查 YUM 是否已安装: yum list installed | grep yum 如果输出中包含 yum,则说明 YUM 已安装。 2. 卸载旧版本的 YUM(如有必要) 如果需要重新安装 YUM,可以先卸载旧版本&…...
对免认证服务提供apikey验证
一些服务不带认证,凡是可以访问到服务端口,都可以正常使用该服务,方便是方便,但是不够安全。 比如ollama默认安装后就是这样。现在据说网上扫一下端口11434,免apikey的ollama服务一大堆。。。 那我们怎样将本机安装的o…...
数据库驱动免费下载(Oracle、Mysql、达梦、Postgresql)
数据库驱动找起来好麻烦,我整理到了一起,需要的朋友免费下载:驱动下载 目前收录了Oracle、Mysql、达梦、Postgresql的数据库驱动的多个版本,后续可能会分享更多。...
OceanBase 初探学习历程之——安装部署
一、介绍 OceanBase 数据库是一个原生的分布式关系数据库,它是完全由阿里巴巴和蚂蚁集团自主研发 的项目。OceanBase 数据库构建在通用服务器集群上,基于 Paxos 协议和分布式架构,提供 金融级高可用和线性伸缩能力,不依赖特定硬件…...
Windows 下免费开源的多格式文件差异对比工具
软件介绍 有这样一款诞生于 2000 年、专为 Windows 系统打造的开源免费工具,截至 2025 年 1 月已更新至 2.16.46 版本,它就是文件与文件夹比较的得力助手。 其支持文本文件、Word、Excel、PPT 网页、图像等多种格式对比,利用高亮显示行内差…...
Vue3+element UI:使用el-dialog时,对话框不出现解决方案
解决方案:在<el-dialog>标签中,添加:append-to-body“true”*,对话框即可弹出。*...
思源宋体CN终极指南:从开源字体到设计利器的完整蜕变
思源宋体CN终极指南:从开源字体到设计利器的完整蜕变 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 你是否曾为寻找一款既专业又免费的中文字体而烦恼?在数字设…...
S32K148开发效率翻倍秘籍:活用S32KDS的Pin Mux、代码生成与Gitee开源例程
S32K148开发效率翻倍秘籍:活用S32KDS的Pin Mux、代码生成与Gitee开源例程 对于已经掌握S32K148基础开发的工程师来说,如何从"能跑通Demo"进阶到"高效完成项目"是一个关键跃迁。本文将聚焦三个核心效率工具链——Pin Mux可视化配置、…...
稀疏深度学习编译框架FuseFlow原理与应用
1. 稀疏深度学习编译框架FuseFlow解析稀疏计算已成为现代深度学习系统不可或缺的优化手段。传统密集计算在处理图神经网络、推荐系统等场景时,由于数据本身的稀疏特性,会浪费大量计算资源在零值运算上。FuseFlow作为面向稀疏深度学习的数据流编译框架&am…...
实测UDOP-large:英文表格解析与数据抽取,提升办公效率
实测UDOP-large:英文表格解析与数据抽取,提升办公效率 1. 引言:表格处理的痛点与解决方案 在日常办公和数据处理中,表格是最常见的信息载体之一。无论是财务报表、实验数据还是业务统计,表格都承载着大量结构化信息。…...
RWKV7-1.5B-world多场景落地:中小企业智能问答、开发者学习、教学演示
RWKV7-1.5B-world多场景落地:中小企业智能问答、开发者学习、教学演示 1. RWKV7-1.5B-world模型概述 RWKV7-1.5B-world是基于第7代RWKV架构的轻量级双语对话模型,拥有15亿参数。这个模型采用了一种创新的线性注意力机制,替代了传统Transfor…...
AI Agent是下一个风口?揭秘能自主完成任务的AI助手,ChatGPT之后最大的革命!
最近两年,“AI Agent"这个词突然刷屏了。朋友圈有人说它是"下一个风口”,科技媒体说它是"ChatGPT之后最大的革命",各种发布会上CEO们也都在扯这个词——但大多数人其实根本不知道它到底是什么东西。 我也一样,…...
去哪个嵌入式培训机构学习比较好
在郑州嵌入式培训领域,结合课程体系、师资实力、实战项目、就业保障四大核心维度,整理出2026年优质机构参考榜,以下是详细对比,供嵌入式学习者参考(数据真实可查,无夸大)。1. 参考依据…...
nli-MiniLM2-L6-H768快速上手:金融研报摘要主题分类(科技/宏观/行业)
nli-MiniLM2-L6-H768快速上手:金融研报摘要主题分类(科技/宏观/行业) 1. 工具简介 nli-MiniLM2-L6-H768是一款基于cross-encoder/nli-MiniLM2-L6-H768轻量级NLI模型开发的本地零样本文本分类工具。它专为解决传统文本分类需要大量标注数据和…...
为什么fastp比Trimmomatic快10倍?深度解析其核心算法原理
为什么fastp比Trimmomatic快10倍?深度解析其核心算法原理 【免费下载链接】fastp An ultra-fast all-in-one FASTQ preprocessor (QC/adapters/trimming/filtering/splitting/merging...) 项目地址: https://gitcode.com/gh_mirrors/fa/fastp 在高通量测序数…...
Handright性能优化:利用多进程并行渲染加速中文手写模拟
Handright性能优化:利用多进程并行渲染加速中文手写模拟 【免费下载链接】Handright A lightweight Python library for simulating Chinese handwriting 项目地址: https://gitcode.com/gh_mirrors/ha/Handright Handright是一款轻量级Python库,…...
