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;
// 创建记忆化数组并初始化为0
int** 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：单词搜索
如果你觉得我自己写的这个代码还不错，请给我点赞、收藏、关注，获取更多算法干货，这也是我之后继续发布高质量算法教程和编程技术帖的最大的动力 感谢大家了！！！！！