数据结构与算法 | 记忆化搜索（Memorize Search）

2023-11-13
福建
本文字数：2833 字
阅读完需：约 9 分钟

在本系列的文章中已经写了二叉树(Binary Tree)、深搜（DFS）与广搜（BFS）、哈希表（Hash Table）等等，计划接下来要写的是动态规划（Dynamic Programming，DP），它算得上是最灵活的一种算法。回忆笔者学习动态规划的时候，最开始接触的是经典的 “01 背包” 问题；不过现在想起来，以“01 背包问题”作为初次接触的动态规划算法的问题_并不友好_；花费了不少时间才慢慢感悟到动态规划算法的核心思想。

先前的文章中涉及了不少搜索算法，在搜索算法上融入动态规划算法思想的记忆化搜索（Memorize Search）不妨是一个不错的_承前启后_的选择。相对于 “01 背包”类问题，记忆化搜索对初学者理解动态规划更友好，也能更好的感受到其魅力所在。

记忆化搜索，所谓 “记忆” 引用 Geeksforgeeks 网站上介绍记忆搜索原文中一句话就是 “to transform the results of a function into something to remember.” 把函数的结果存储下来作为 “记忆”。将“记忆”应用于搜索算法上，也就是搜索到有记录了函数结果的地方，其实就不需要再进行函数计算，直接返回 “记忆” 的结果即可。

记忆化搜索是一种自顶向下（Top-Down）分析的算法，文字描述过于悬浮于理论，保持本系列文风且用算法题来看下记忆化搜索算法具体的内容。

自顶向下（Top-Down）

LeetCode 329. 矩阵中的最长递增路径【困难】

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。（即不允许环绕）。

直接顺着题意进行分析，找到 “最长递增路径” 直接用搜索遍历，把 matrix 每个单元格的最长递增路径都计算下，返回其中最长的路径。不妨就假设下有一个 search 的函数能够计算出以当前单元格为起点的最长递增路径长度。遍历过程中的最大长度存储再 max 中，最后返回即可，代码如下：

// 假设中的函数public int search(int[][] matrix,int x,int y){	int max;	return max;}
public int longestIncreasingPath(int[][] matrix) {
        int max = 0;        for (int i = 0; i < matrix.length; i++) {            for (int j = 0; j < matrix[0].length; j++) {            	//（i，j）格的最长递增路径长度                 max = Math.max(max,search(matrix,i,j));            }        }        return max;    }

复制代码

问题开始关键点现在变成了 search 函数的实现；接着顺着题意分析，可以往上，下，左，右四个方向移动.首先考虑一个方向情况，只往上方向移动且可以往上移动（上方相邻的单元格大于当前单元格，递增），那么此时当前单元格的最大路径长度就是 上方单元格的最大路径 + 1，其中1代表当前单元格。

public int search(int[][] matrix,int x,int y){    	int number = matrix[x][y],up = 1;
	// 保障可以往“上”移动， x-1 没有越边界（ x > 0 ）	// 且是 递增的 matrix[x-1][y] > number    if( x > 0 && matrix[x-1][y] > number ){
    	 // 递归调用，同类子问题，（x-1，y）格的最长递增路径长度          up += search( matrix, x-1, y );    }
	return up;}

复制代码

如此，扩展到四个方向，最终当前单元格最大路径就是四个方向中取最大的返回。

public int search(int[][] matrix,int x,int y){
        int number = matrix[x][y],up = 1,down =1,left=1,right=1;
        if(x>0 && matrix[x-1][y] > number){            up += search(matrix,x-1,y);        }        if(x+1<matrix.length && matrix[x+1][y] > number){            down += search(matrix,x+1,y);        }        if(y+1<matrix[0].length && matrix[x][y+1] > number){            right += search(matrix,x,y+1);        }        if(y>0 && matrix[x][y-1] > number){            left += search(matrix,x,y-1);        }
        return Math.max(Math.max(up,down),Math.max(right,left));}

复制代码

实现到这里按照搜索思路的算法已经完成；不过会发现性能不高，分析过程会发现调用 search 函数时候，同样一格位置会计算多次。此时联系想想先前提到的 “记忆” ，把函数的结果存储下来作为 “记忆”，也就是用一个二维数组 cahce 缓存起来已经计算过单元的结果。

search 实现改为 (cache 需要在 longestIncreasingPath 根据 matrx 大小 new 下，这里略) ，代码如下：

public int[][] cache = null;
public int search(int[][] matrix,int x,int y){
        if(0 != cache[x][y])            return cache[x][y];
        int number = matrix[x][y],up = 1,down =1,left=1,right=1;        if(x>0 && matrix[x-1][y] > number){            up += search(matrix,x-1,y);        }        if(x+1<matrix.length && matrix[x+1][y] > number){            down += search(matrix,x+1,y);        }        if(y+1<matrix[0].length && matrix[x][y+1] > number){            right += search(matrix,x,y+1);        }        if(y>0 && matrix[x][y-1] > number){            left += search(matrix,x,y-1);        }        // 存储 “记忆”        cache[x][y] = Math.max(Math.max(up,down),Math.max(right,left));        return cache[x][y];}

复制代码

到此，已经按照记忆化搜索算法思路完成了问题的解决。

回顾下记忆化搜索解题过程，我们是从算法问题出发 -> 分析需要完成的计算（子问题）-> 进一步进行解决。这其实就是 自顶向下（Top-Down）的思考方式。

记忆化搜索与动态规划

再来看"记忆"，cache[x][y] 所记录的是 x,y 这个单元格已经计算过的 最大路径长度。当前单元格 的最大路径长度使用上、下、左、右四个方向上的单元格 最大路径长度来进行计算 ,使用"记忆" 其实就是在使用子问题的最优解。

current_max = Max( up+1, down+1, left+1, right+1 )

复制代码

另外一个角度描述，规划决策 当前单元格的最大路径是根据（上、下、左、右）相邻四个方向上的单元格最大路径进行的计算。相邻四个方向上的最大路径（子问题最优解）并非一开始静态写入下来，而是在程序运行过程中至少计算一次存储下来，可看作 动态的计算。根据动态计算子问题最优结果来进行规划决策当前最优结果，也就是所谓 动态规划（Dynamic Programming）的字面意思。

可以多体会下： 解决最优化问题，根据子问题的最优结果 规划决策 -> 当前问题最优结果 -> 进而求解最初问题。

所以有一种说法就是：记忆化搜索是动态规划 自顶向下（Top-Down）分析的一种实现形式，通常用递归来实现。

最后总结本文

本系列文章中写此篇承前启后的思考，记忆化搜索的基本概念；

通过一道题演示 自顶向下（Top-Down）的分析，实际应用记忆化搜索解决具体算法问题；

解读记忆化搜索与动态规划的关系，以及动态规划一些概念。

文章转载自：Java研究者

原文链接：https://www.cnblogs.com/jzhlin/p/Memorize_Search.html

发布于: 刚刚阅读数: 5

不在线第一只蜗牛

关注

还未添加个人签名 2023-06-19 加入

还未添加个人简介

发布

暂无评论

创作场景

数据结构与算法 | 记忆化搜索（Memorize Search）

自顶向下（Top-Down）

LeetCode 329. 矩阵中的最长递增路径【困难】

记忆化搜索 与 动态规划

最后总结本文

不在线第一只蜗牛

评论

记忆化搜索与动态规划