[特殊字符] 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”*,对话框即可弹出。*...
让聊天记忆永存:打造你的专属数字对话档案馆
让聊天记忆永存:打造你的专属数字对话档案馆 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeChatMsg …...
别再只叫它八木天线了!聊聊Yagi-Uda天线的历史、原理与DIY实战(附尺寸计算)
从命名争议到卫星通信:Yagi-Uda天线的技术演进与自制指南 在业余无线电爱好者的聚会中,你总能听到人们兴奋地讨论着"八木天线"——这种高增益定向天线几乎是远距离通信的代名词。但有趣的是,大多数讨论者都忽略了一个关键事实&…...
从零到一:在Ubuntu上为SpaceMouse配置开源驱动并集成Python/Robosuite
1. 为什么需要为SpaceMouse配置开源驱动? 如果你手头有一台3Dconnexion的SpaceMouse,想在Ubuntu系统上使用它来控制机器人仿真环境,可能会遇到一个尴尬的问题:官方早在2014年就停止了对Linux驱动的支持。这意味着你无法直接使用Sp…...
避坑指南:STM32软件I2C读取MPU6050数据老是不对?可能是这5个细节没做好
STM32软件I2C读取MPU6050数据异常排查实战手册 深夜调试嵌入式系统时,最令人抓狂的莫过于硬件连接看似正常,但传感器数据死活读不出来。上周我就遇到了这样的困境:用STM32的软件模拟I2C读取MPU6050时,OLED屏幕上要么显示一堆乱码&…...
别再只跑Demo了!手把手教你用HPatches数据集实战评测你的局部描述子算法
别再只跑Demo了!手把手教你用HPatches数据集实战评测你的局部描述子算法 当你花费数周时间开发出一个新的局部描述子算法,兴奋地在Demo图像上看到不错的匹配效果时,是否曾思考过:这个算法在真实场景下的表现究竟如何?…...
零刻EQ12 N100双网口AIO实战:从ESXI部署到多系统融合
1. 零刻EQ12 N100双网口AIO方案解析 第一次接触零刻EQ12 N100这款小主机时,我就被它的双2.5G网口设计吸引了。这种配置在家庭网络改造和轻量级数据中心建设中简直就是神器。AIO(All In One)方案的核心思想就是把路由、存储、虚拟化等功能整合…...
3D Face HRN部署案例:为AI绘画平台增加‘2D→3D人脸’创意增强功能模块
3D Face HRN部署案例:为AI绘画平台增加‘2D→3D人脸’创意增强功能模块 想象一下,你是一个AI绘画平台的开发者。用户上传了一张精美的2D人像画作,但总觉得少了点什么——画面是平面的,缺乏立体感和深度。如果能一键将这张2D人像转…...
别再死记硬背Ceph架构图了!从PG、Pool到CRUSH,用大白话讲清数据到底怎么存的
从快递分拣系统理解Ceph存储:PG、Pool与CRUSH的实战逻辑 当你第一次看到Ceph架构图中那些密密麻麻的PG、Pool、OSD和CRUSH规则时,是否感觉像在解读天书?别担心,这就像让一个从没见过快递分拣中心的人直接看自动化物流系统的电路图…...
Real-Anime-Z入门指南:从服务器IP访问7860到生成首张图的5分钟全流程
Real-Anime-Z入门指南:从服务器IP访问7860到生成首张图的5分钟全流程 1. 项目概述 Real-Anime-Z是一款基于Stable Diffusion技术的2.5D风格图像生成模型,完美融合了写实质感与动漫美感。这个模型系列由23个LoRA变体组成,可以叠加在Z-Image基…...
MicroPython v1.24新特性解析:RISC-V优化与物联网芯片支持
1. MicroPython v1.24版本深度解析MicroPython作为嵌入式开发领域的轻量级Python实现,其最新v1.24版本带来了多项重要更新。这次升级不仅增加了对两款热门微控制器的支持,还在RISC-V架构优化、实时操作系统适配等方面有显著改进。对于嵌入式开发者而言&a…...
