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

从经典力扣题发掘DFS与记忆化搜索的本质 -从矩阵最长递增路径入手一步步探究dfs思维优化与编程深度思考

news 来源：原创 2025/7/19 3:18:52

1引子：

DFS和递归法的一道经典例题矩阵最长递增子序列这个题写完之后脑袋产生了许多突发奇想：

1 第一个堆栈代码段这些底层C语言内部管理的工具它是怎么进行内存分配的？能不能深究？
2 第二个这个DFS和计划数组存储的思路到底抽象了哪种思维？能不能发散到其他算法数据结构的面试题中？或者说能不能在其他的编程中应用到这种思维抽象出一个公有的编程范式思维范式应用到其他的任何领域包括生活中？
3 是就有了这篇博文希望大家一起和我探讨一下

2 题描述

给定一个 n 行 m 列的矩阵，矩阵内所有数均为非负整数。需要找到一条最长路径，使得这条路径上的元素是严格递增的。路径可以向上、下、左、右四个方向移动，但不能重复访问同一个单元格。

示例：
输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：5
解释：最长递增路径为 1->2->3->6->9

1暴力 DFS 解法

首先想到的是暴力 DFS，从每个单元格出发，尝试所有可能的路径：

#include <stdio.h>
#include <stdlib.h>// 方向数组：上、下、左、右
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 深度优先搜索函数
int dfs(int** matrix, int rows, int cols, int r, int c, int prev) {// 检查边界条件和递增条件if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r][c] <= prev) {return 0;}int maxPath = 0;// 遍历四个方向for (int i = 0; i < 4; i++) {int nr = r + dirs[i][0];int nc = c + dirs[i][1];int path = 1 + dfs(matrix, rows, cols, nr, nc, matrix[r][c]);if (path > maxPath) {maxPath = path;}}return maxPath;
}// 主函数：计算最长递增路径
int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {if (matrixSize == 0 || *matrixColSize == 0) {return 0;}int rows = matrixSize;int cols = *matrixColSize;int maxLength = 0;// 遍历每个单元格作为起点for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {int length = dfs(matrix, rows, cols, r, c, -1);if (length > maxLength) {maxLength = length;}}}return maxLength;
}

复杂度分析：

时间复杂度：O (4^(n*m))，每个单元格有 4 个方向可以选择
空间复杂度：O (n*m)，递归栈的深度最大为矩阵的大小

问题： 这种解法会导致大量重复计算，比如从不同路径到达同一个单元格时，会重复计算该单元格的最长路径。

2 记忆化搜索优化

为了避免重复计算，可以使用记忆化搜索：用一个二维数组memo记录每个单元格的最长递增路径长度。当访问一个单元格时，如果该单元格的结果已经计算过，直接返回结果，否则进行计算并保存结果。

#include <stdio.h>
#include <stdlib.h>// 方向数组：上、下、左、右
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 深度优先搜索函数
int dfs(int** matrix, int rows, int cols, int r, int c, int** memo) {// 如果已经计算过，直接返回结果if (memo[r][c] != 0) {return memo[r][c];}int maxPath = 1;  // 至少包含当前单元格// 遍历四个方向for (int i = 0; i < 4; i++) {int nr = r + dirs[i][0];int nc = c + dirs[i][1];// 检查边界条件和递增条件if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {int path = 1 + dfs(matrix, rows, cols, nr, nc, memo);if (path > maxPath) {maxPath = path;}}}// 记录当前单元格的最长路径memo[r][c] = maxPath;return maxPath;
}// 主函数：计算最长递增路径
int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {if (matrixSize == 0 || *matrixColSize == 0) {return 0;}int rows = matrixSize;int cols = *matrixColSize;// 创建记忆化数组并初始化为0int** memo = (int**)malloc(rows * sizeof(int*));for (int i = 0; i < rows; i++) {memo[i] = (int*)calloc(cols, sizeof(int));}int maxLength = 0;// 遍历每个单元格作为起点for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {int length = dfs(matrix, rows, cols, r, c, memo);if (length > maxLength) {maxLength = length;}}}// 释放内存for (int i = 0; i < rows; i++) {free(memo[i]);}free(memo);return maxLength;
}

复杂度分析：

时间复杂度：O (n*m)，每个单元格只需要计算一次
空间复杂度：O (n*m)，主要用于存储记忆化数组

3 记忆化搜索的本质

记忆化搜索实际上是动态规划的递归实现，它的核心思想是

重叠子问题：原问题可以分解为大量重复的子问题
最优子结构：问题的最优解包含子问题的最优解
状态保存：用一个数组保存已经解决的子问题的解

在这个问题中，每个单元格的最长递增路径就是一个子问题，我们通过记忆化数组避免了重复计算，将指数级时间复杂度优化到了线性级别。

4 vscode实际我的测试代码：

1 我的测试

输入矩阵：

[[9, 9, 4],[6, 6, 8],[2, 1, 1]]

步骤解析：

从单元格 (0,0) 开始，值为 9，四个方向都无法移动，路径长度为 1
从单元格 (0,1) 开始，值为 9，同样无法移动，路径长度为 1
从单元格 (1,0) 开始，值为 6，可以移动到 (2,0)，继续递归计算...
当计算到单元格 (2,1) 时，值为 1，可以移动到 (2,0)，但 (2,0) 的结果已经计算过，直接使用保存的结果

最终，整个矩阵的最长递增路径为 1->2->6->8->9，长度 5

通过这个问题，我们深入理解了 DFS 和记忆化搜索的结合使用。当遇到需要大量重复计算的问题时，记忆化搜索是一种非常有效的优化方法。关键在于识别问题中的重叠子问题，并设计合适的状态保存方式。

希望这篇文章能帮助你更好地理解深度优先搜索和动态规划的思想，如果你有任何疑问或更好的解法，欢迎在评论区留言讨论！

4.2 举一反三我的习惯...

如果你对这类问题感兴趣，可以尝试以下我做的其他教程题目

力扣 329：矩阵中的最长递增路径本题进阶版
力扣 62：不同路径
力扣 64：最小路径和
力扣 79：单词搜索

如果你觉得我自己写的这个代码还不错，请给我点赞、收藏、关注，获取更多算法干货，这也是我之后继续发布高质量算法教程和编程技术帖的最大的动力感谢大家了！！！！！

从经典力扣题发掘DFS与记忆化搜索的本质 -从矩阵最长递增路径入手一步步探究dfs思维优化与编程深度思考

1引子： DFS和递归法的一道经典例题矩阵最长递增子序列这个题写完之后脑袋产生了许多突发奇想： 1 第一个堆栈代码段这些底层C语言内部管理的工具它是怎么进行内存分配的？能不能深究？ 2 第二个这个DFS和计划数组存储的思路到底抽象…...

编程日记 2025/7/19 3:18:52

我开源了一个免费在线工具！UIED Tools

UIED Tools - 免费在线工具集合最近更新：修改了文档说明，优化了项目结构介绍这是设计师转开发的第一个开源项目，bug和代码规范可能有些欠缺。这是一个功能丰富的免费在线工具集合网站，集成了多种实用工具，包括 AI …...

编程日记 2025/7/19 3:06:02

geoserver发布arcgis瓦片地图服务（最新版本）

第一步：下载geoserver服务，进入bin目录启动需要提前安装好JDK环境，1.8及以上版本安装完成，页面访问端口，进入控制台界面,默认用户名密码admin/geoserver 第二步：下载地图破解版全能电子地图下载器&…...

编程日记 2025/7/18 13:58:04

RN 鸿蒙混合开发实践(踩坑)

#三方框架# #React Native # 1 。环境配置； 安装 DevEco 开发工具； Node 版本16； hdc环境配置 hdc 是 OpenHarmony 为开发人员提供的用于调试的命令行工具，鸿蒙 React Native 工程使用 hdc 进行真机调试。hdc 工具通过 OpenHa…...

编程日记 2025/7/18 20:51:52

2025年阿里云ACP大数据分析师认证模拟试题（附答案解析）

这篇文章的内容是阿里云ACP大数据分析师认证考试的模拟试题。所有模拟试题由AI自动生成，主要为了练习和巩固知识，并非所谓的 “题库”，考试中如果出现同样试题那真是纯属巧合。 1、ABC公司现有大量的图片和视频信息，以下哪种产…...

编程日记 2025/7/19 1:50:18

go语言实现IP归属地查询

效果: 实现代码main.go package mainimport ("encoding/json""fmt""io/ioutil""net/http""os" )type AreaData struct {Continent string json:"continent"Country string json:"country"ZipCode …...

编程日记 2025/7/19 3:11:31

Qt中解决UI线程阻塞导致弹窗无法显示的两种方法

在Qt应用程序开发中，我们经常会遇到这样的问题：当执行一个耗时操作时，整个界面会卡住，无法响应任何用户操作，甚至连一个简单的提示弹窗都无法正常显示。本文将介绍两种解决这个问题的方法，并通过完整的代码示例进行说明。问题描述先来看一个常见的错误示例： #inclu…...

编程日记 2025/7/17 14:14:36

位运算题目：黑板异或游戏

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题：黑板异或游戏出处：810. 黑板异或游戏难度 8 级题目描述要求给定一个整数数组 nums \texttt{nums} nums，表示写在黑板…...

编程日记 2025/7/18 18:28:55

LegoGPT，卡内基梅隆大学推出的乐高积木设计模型

LegoGPT 是由卡内基梅隆大学开发的一款创新性乐高积木设计模型，能够根据用户的文本提示生成结构稳固、可组装的乐高模型。该模型基于自回归语言模型和大规模乐高设计数据集进行训练，用户只需输入简单的文字描述，LegoGPT 就能逐步构建出物理稳…...

编程日记 2025/7/19 3:03:55

深度 |国产操作系统“破茧而出”：鸿蒙电脑填补自主生态空白

真心为国内能有像华为这样的技术型公司而自豪，一步步突围技术封锁。从这篇信息，可以给软件从业者一个启示：鸿蒙生态将是一个新的机会，值得好好把握。鸿蒙电脑正成为中国电子信息技术新坐标。超10亿鸿蒙生态设备、2800家鸿蒙智…...

编程日记 2025/7/19 2:56:03

【Python】Python常用数据类型判断方法详解

在Python编程中，准确判断数据类型是处理逻辑分支、类型转换和异常处理的基础。本文结合核心方法与实践场景，系统介绍type()、isinstance()等常用判断方式，并分析其适用性与最佳实践。一、直接类型判断方法 type()函数 • 功能：返回对象的精确类型，适用于简单类型判断。 •…...

编程日记 2025/7/19 2:56:02

【美国将取消对能源之星支持严重影响AI服务器】

1992年美国政府在共和党执政期间推出了影响深远的“能源之星”计划（Energy Star），很多人可能并不知道能源执行计划，但这个蓝色星星标签估计大多数人都不会陌生。能源之星计划从推出以来不止得到各类消费电子制造商认可&#xff0c…...

编程日记 2025/7/19 2:58:00

《 C++ 点滴漫谈：三十七》左值？右值？完美转发？C++ 引用的真相超乎你想象！

摘要本文全面系统地讲解了 C 中的引用机制，涵盖左值引用、右值引用、引用折叠、完美转发等核心概念，并深入探讨其底层实现原理及工程实践应用。通过详细的示例与对比，读者不仅能掌握引用的语法规则和使用技巧，还能理解引用在性能…...

编程日记 2025/7/19 3:02:56

【生产实践】Linux中/usr/bin、/usr/sbin与/usr/local的关系解析（2025年技术规范）

一、核心定位与功能划分 /usr/bin：用户级通用命令库 • 定位：存储系统预装的用户级可执行文件，这些命令通常由Linux发行版官方软件包管理器（如APT、YUM）安装，属于系统默认功能的一部分。 • 示例命令&#…...

编程日记 2025/7/19 2:52:13

数据可视化：用一张图讲好一个故事

在这个信息爆炸的时代，数据无处不在，但如何让复杂的数据变得通俗易懂？数据可视化就是一把神奇的钥匙。它不仅能将枯燥的数字转化为生动的图像，还能挖掘出数据背后隐藏的故事。然而，很多人对数据可视化的理解还停留在表…...

编程日记 2025/7/19 2:44:27

C++获取目录中所有图片路径的函数get_image_paths解析

本文将全面解析一个用于获取目录中图片路径的C函数get_image_paths，从基础语法到高级概念，涵盖C标准库、文件系统操作、异常处理等多个方面。原始代码 std::vector<std::string> get_image_paths(const std::string& directory_path) {log_…...

编程日记 2025/7/18 7:18:02

物联网无线传感方向专业词汇解释

涡旋电磁波(VEMW)：一种具有轨道角动量的电磁波，其特性在于能够在传播过程中携带额外的相位信息，从而增加通信系统的容量和灵活性。波前：波动传播过程中，同一时刻振动相位相同的所有点构成的几何曲面，代表波…...

编程日记 2025/7/16 15:26:21

【C语言指针超详解(五)】--回调函数，qsort函数的理解和使用，qsort函数的模拟实现

目录一.回调函数 1.1--回调函数的概念 1.2--回调函数改造计算器程序二.qsort函数的理解和使用 2.1--qsort函数的理解 2.2--使用qsort函数排序整型数据 2.3--使用qsort函数排序结构数据三.qsort函数的模拟实现 🔥个人主页：草莓熊Lotso的个人主…...

编程日记 2025/7/19 2:45:28

【Linux网络】————HTTP协议详解

作者主页： 作者主页本篇博客专栏：Linux 创作时间 ：2025年5月11日 1. HTTP 协议介绍基本介绍： http协议全称：超文本传输协议，适用于从万维网服务器传输超文本到本地的传送协议。HTTP是一种应用层协议…...

编程日记 2025/7/19 3:15:40

使用WinSW工具将exe注册为window服务

下载工具WinSW(工具在GitHub上打不开就需要魔法VPN) 文件准备将以下文件放在同一个目录（例如：WebSocketService 文件夹）中： WebScoket.exe WinSW-x64.exe WebScoketService.xml ← 服务配置文件 install_service.bat ←…...

编程日记 2025/7/19 2:50:09

远程命令执行RCE概述

远程命令执行RCE诞生于1997年，比SQL注入早1年，据说当时的程序员发现在网站里可以随意的删除网页，就像删除本地文件一样简单，但是这种场景相对不多，因此没有SQL注入广泛，早期的web攻击像现在的护网一样&…...

编程日记 2025/7/19 2:57:59

在 .NET 8 开发的WinForms 程序中展示程序版本号的几种方式

前言欢迎关注dotnet研习社，今天我们讨论一个Winform开发中的一个常见的需求内容“关于程序的版本号显示”。在 WinForms 桌面应用程序开发中，向用户显示当前程序的版本号是一个常见的需求，尤其是在产品发布、更新提示或技术支持场景中尤为…...

编程日记 2025/7/19 2:57:03

[特殊字符] Spring Cloud 微服务项目中 common 模块依赖导致网关启动失败的排查与解决

在进行微服务开发时，我们通常会抽取一个 common 公共模块，封装一些通用配置类、工具类、拦截器、常用组件依赖等，供多个微服务共享使用。但近期在实际开发中，出现了一个典型问题：在 Gateway 网关模块中引入 common 后…...

编程日记 2025/7/19 2:46:28

Java SpringMVC 和 MyBatis 整合关键配置详解

目录一、数据源配置二、MyBatis 工厂配置三、Mapper 扫描配置四、SpringMVC 配置五、整合示例实体类Mapper 接口Mapper XML 文件Service 类控制器JSP 页面六、总结在 Java Web 开发中，SpringMVC 和 MyBatis 是两个常用框架。SpringMVC 负责 Web 层的请求处理和视图渲染，MyBa…...

编程日记 2025/7/18 19:07:25

24.（vue3.x+vite）引入组件并动态挂载（mount）

示例截图组件代码： <template><div><div>{{message }}</div>...

编程日记 2025/7/19 3:16:59

Linux 软件包|服务管理

rpm 指令备注rpm -qa查看已安装软件，可以结合grep过滤查找rpm -e firefox卸载firefoxrpm -ivh firefox-115.12.0-1.el7.centos.i686.rpm安装gcc（只能离线安装） yum 能够从指定的服务器自动下载 RPM 包并且安装指令备注yum list列出所有可…...

编程日记 2025/7/17 17:27:16

前端上传el-upload、原生input本地文件pdf格式(纯前端预览本地文件不走后端接口）

前端实现本地文件上传与预览（PDF格式展示）不走后端接口实现步骤第一步：文件选择使用前端原生input上传本地文件，或者是el-upload组件实现文件选择功能，核心在于文件渲染处理。（input只不过可以自定义样…...

编程日记 2025/7/13 16:47:58

TestNG接口自动化

第一章、 Rest assured接口测试框架一、概述接口自动化的框架，主要是用来做接口自动化测试，返回的报文都是JSON 语法比较简单，只需要掌握常用的方法用例运行的速度非常快断言的机制 Json 封装相关方法，jsonpath，x…...

编程日记 2025/7/19 2:57:03

Parasoft C++Test软件单元测试_实例讲解（指针类型的处理）

系列文章目录 Parasoft C++Test软件静态分析：操作指南（编码规范、质量度量）、常见问题及处理 Parasoft C++Test软件单元测试：操作指南、实例讲解、常见问题及处理 Parasoft C++Test软件集成测试：操作指南、实例讲解、常见问题及处理进阶扩展：自动生成静态分析文档、自动…...

编程日记 2025/7/16 14:23:46

ngx_http_keyval_module动态键值管理

一、模块安装与验证检查模块是否可用 nginx -V 2>&1 | grep --color -o ngx_http_keyval_module如果看到 ngx_http_keyval_module，说明模块已编译进 NGINX。若未找到，请联系你的 NGINX 供应商，获取商业版或重新编译并启用该模块&am…...

编程日记 2025/7/17 7:47:19

面试篇：Spring MVC

基础概念什么是Spring MVC？ Spring MVC 是 Spring Framework 提供的一个基于 Servlet 的 Web 框架，属于 MVC（Model-View-Controller）架构的一种实现。它通过 DispatcherServlet 作为前端控制器，对请求进行分发和调度…...

编程日记 2025/7/19 1:09:09

目录 1.string::find(char ch,size_t pos0) const的模拟实现 2.string::find(const char* str,size_t pos0) const的模拟实现 3.string::size() const和string::capacity() const的模拟实现 4.string::operator[] (size_t pos)和string::operator[] (size_t pos) const的模拟…...

编程日记 2025/7/13 21:23:24

接口出现请求参数格式错误的解决方法

目录前言1. 问题所示2. 原理分析3. 解决方法前言 🤟 找工作，来万码优才：👉 #小程序://万码优才/r6rqmzDaXpYkJZF 爬虫神器，无代码爬取，就来：bright.cn Java基本知识： java框架零基础从入门到精通的学习路线附开源项目面经等（超全）【Java项目】实战CRUD的功能整理…...

编程日记 2025/7/18 13:39:39

MYSQL时间函数、group by 和partition by的区别、组内编号leetcode学习

mysql时间函数 select now(); --当前时间 select current_date() --当前日期 select current_timestamp --同now()select date(2025-04-14 12:34:56) --提取日期部分：2025-04-14 select datediff(2025-4-14,2025-04-10) 日期相差四天 select date_sub(2024-04-14,…...

编程日记 2025/7/16 19:08:31

OpenCV 的 CUDA 模块中用于将一个多通道 GpuMat 图像拆分成多个单通道图像的函数split()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述 cv::cuda::split 是 OpenCV CUDA 模块中的一个函数，用于将一个多通道的 GpuMat 图像拆分成多个单通道的 GpuMat 图像。这个函数是 CP…...

编程日记 2025/7/15 11:45:38

吴恩达机器学习笔记：单变量线性回归

通过一个例子来开始：这个例子是预测住房价格的，我们要使用一个数据集，数据集包含俄勒冈州波特兰市的住房价格。根据不同房屋尺寸所售出的价格，画出我的数据集。比方说，如果房子是 1250 平方尺大小，你要告诉…...

编程日记 2025/7/17 0:27:25

UI自动化测试框架：PO 模式+数据驱动

🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快 1. PO 设计模式简介什么是 PO 模式？ PO（PageObject）设计模式将某个页面的所有元素对象定位和对元素对象的操作封装成…...

编程日记 2025/7/16 7:57:46

NestJS 知识框架

一、核心概念 1. 架构基础基于 Express/Fastify 的 Node.js 框架采用模块化设计使用 TypeScript 构建（也支持 JavaScript） 借鉴 Angular 的设计理念 2. 主要组件模块 (Module): 应用的基本组织单元控制器 (Controller): 处理 HTTP 请求服务…...

编程日记 2025/7/16 19:33:00

Porting Linux to a new processor architecture, part 1: The basics

Although a simple port may count as little as 4000 lines of code—exactly 3,775 for the mmu-less Hitachi 8/300 recently reintroduced in Linux 4.2-rc1—getting the Linux kernel running on a new processor architecture is a difficult process. Worse still, the…...

编程日记 2025/7/16 1:45:15