在本系列的文章中已经写了二叉树(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)分析的算法,文字描述过于悬浮于理论,保持本系列文风且用算法题来看下记忆化搜索算法具体的内容。
给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外。(即不允许环绕)。
// 假设中的函数
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;
}
上方单元格的最大路径 + 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 实现改为 (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)分析的一种实现形式,通常用递归来实现。
下一篇咱们再一起继续解读 动态规划(Dynamic Programming) ,欢迎关注 Java研究者专栏、博客、公众号等
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。