目录引入记忆化搜索解决的是什么问题一、斐波那契数最简单的一维缓存二、不同路径坐标就是完整状态三、最长递增子序列按起始下标缓存四、猜数字 II区间就是状态五、矩阵中的最长递增路径坐标缓存加方向搜索六、从多道题中归纳记忆化搜索规律七、易错点八、本篇总结引入记忆化搜索解决的是什么问题有些递归题的递归关系没有问题但不同分支会反复到达同一个状态。普通递归每次都重新计算时间会迅速增加。记忆化搜索就是在递归的基础上增加缓存某个状态第一次计算时保存答案之后再次遇到完全相同的状态时直接返回缓存结果。memo是 memory 的缩写可以理解为记忆表或缓存表dfs通常表示从当前状态继续搜索row和col表示网格坐标index表示数组中的起始下标left和right表示区间边界ret表示当前方法最终返回的答案。记忆化搜索和visited的作用不同。visited主要限制一条当前路径不能重复访问memo保存一个状态已经计算出的答案。前者是访问限制后者是计算结果缓存。一、斐波那契数最简单的一维缓存题目描述题目斐波那契数。LeetCode 509。斐波那契数列定义为F(0) 0、F(1) 1之后每一项等于前两项之和。给定n返回F(n)。题目链接斐波那契数算法原理普通递归计算F(n)时会递归计算F(n - 1)和F(n - 2)。这两个分支又会重复计算很多相同的小数字。这里的状态只有一个n所以用一维数组memo[n]保存结果。第一次计算后写入缓存后面再次遇到同一个n时直接返回。-1作为“还没有计算”的标记因为合法答案不会是负数。Java 代码import java.util.Arrays; class Solution { public int fib(int n) { int[] memo new int[n 1]; Arrays.fill(memo, -1); return dfs(n, memo); } private int dfs(int n, int[] memo) { if (n 0) return 0; if (n 1) return 1; if (memo[n] ! -1) return memo[n]; memo[n] dfs(n - 1, memo) dfs(n - 2, memo); return memo[n]; } }代码说明Arrays.fill(memo, -1)把缓存数组的每个位置初始化为 -1。Arrays是 Java 的数组工具类fill用于批量填充数组。dfs(n, memo)的含义是返回第n个斐波那契数。出口是 0 和 1在递归展开前先检查memo[n]算出答案后保存到memo[n]。二、不同路径坐标就是完整状态题目描述题目不同路径。LeetCode 62。一个机器人位于m * n网格的左上角只能向右或向下移动求它到达右下角一共有多少条不同路径。题目链接不同路径算法原理从某个坐标(row, col)出发未来只有两种移动向下或向右。因此从这个坐标走到终点的路径数只由坐标决定不需要知道之前是怎么走来的。越界时没有路径返回 0到达右下角时找到一条路径返回 1。由于很多路径会重复到达同一个坐标可以用memo[row][col]缓存从该坐标出发的答案。Java 代码class Solution { public int uniquePaths(int m, int n) { int[][] memo new int[m][n]; return dfs(0, 0, m, n, memo); } private int dfs(int row, int col, int m, int n, int[][] memo) { if (row m || col n) return 0; if (row m - 1 col n - 1) return 1; if (memo[row][col] ! 0) { return memo[row][col]; } memo[row][col] dfs(row 1, col, m, n, memo) dfs(row, col 1, m, n, memo); return memo[row][col]; } }代码说明dfs(row, col, m, n, memo)表示从当前位置走到右下角的路径数。因为合法路径数量是正数所以这里可以用 0 表示“还没有计算”。这和斐波那契的缓存结构不同但流程完全相同先判断出口再查缓存递归计算更小状态最后把结果保存到当前状态的位置。三、最长递增子序列按起始下标缓存题目描述题目最长递增子序列。LeetCode 300。给定一个整数数组找出其中最长的严格递增子序列长度。子序列不要求连续但元素在原数组中的相对顺序不能改变。题目链接最长递增子序列算法原理可以定义dfs(index)为“以nums[index]作为第一个元素时后面能得到的最长递增子序列长度”。之后只需要向右寻找比nums[index]大的next把它接到当前序列后面。只要起始下标相同后续可以选择的数组范围和递增条件就相同所以缓存状态只需要index不需要把已经构造的完整序列放进memo。Java 代码class Solution { public int lengthOfLIS(int[] nums) { int[] memo new int[nums.length]; int ret 0; for (int index 0; index nums.length; index) { ret Math.max(ret, dfs(index, nums, memo)); } return ret; } private int dfs(int index, int[] nums, int[] memo) { if (memo[index] ! 0) return memo[index]; int best 1; for (int next index 1; next nums.length; next) { if (nums[next] nums[index]) { best Math.max(best, 1 dfs(next, nums, memo)); } } memo[index] best; return best; } }代码说明index是当前子序列的起始下标next是正在尝试接到后面的下标。每个位置至少能形成长度为 1 的子序列所以best从 1 开始。外层循环让每个下标都作为起点ret保存所有起点中的最大值。Math.max用于保留较大的长度。四、猜数字 II区间就是状态题目描述题目猜数字 II。LeetCode 375。从 1 到n中猜一个数字每次猜错都要支付猜测数字本身的金额并且会得到答案在左侧还是右侧的提示。求保证一定猜中所需要支付的最少金额。题目链接猜数字 II算法原理如果当前还可能的数字范围是[left, right]那么之后的答案只和这个区间有关。因此可以用memo[left][right]保存处理这个区间的最少保证金额。第一次猜guess后目标可能在左区间也可能在右区间。为了保证无论结果落在哪边都能猜中当前猜测的代价要加上左右两边代价的较大值。然后在所有第一次猜法中选择总代价最小的一种。Java 代码class Solution { public int getMoneyAmount(int n) { Integer[][] memo new Integer[n 1][n 1]; return dfs(1, n, memo); } private int dfs(int left, int right, Integer[][] memo) { if (left right) return 0; if (memo[left][right] ! null) { return memo[left][right]; } int ret Integer.MAX_VALUE; for (int guess left; guess right; guess) { int leftCost dfs(left, guess - 1, memo); int rightCost dfs(guess 1, right, memo); int currentCost guess Math.max(leftCost, rightCost); ret Math.min(ret, currentCost); } memo[left][right] ret; return ret; } }代码说明left和right是当前仍可能包含答案的闭区间。区间只有一个数字或为空时不需要再猜返回 0。Integer[][]使用包装类型Integer默认值是null正好可以表示“还没有计算”。Integer.MAX_VALUE是Integer能表示的最大整数适合在求最小值时作为初始值Math.min会保留较小的方案代价。五、矩阵中的最长递增路径坐标缓存加方向搜索题目描述题目矩阵中的最长递增路径。LeetCode 329。给定一个整数矩阵每次可以向上、下、左、右移动但只能移动到严格大于当前值的格子。返回矩阵中的最长递增路径长度。题目链接矩阵中的最长递增路径算法原理从某个坐标出发未来能走多长只由当前位置和矩阵内容决定不取决于之前是怎样走到这里的。因此可以用memo[row][col]保存从该坐标出发的最长递增长度。当前位置本身至少贡献长度 1。向四个方向尝试时只允许进入比当前值大的格子。每个坐标第一次算完后写入缓存外层遍历所有坐标并取最大值。Java 代码class Solution { private static final int[][] DIRECTIONS { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public int longestIncreasingPath(int[][] matrix) { int rows matrix.length; int cols matrix[0].length; int[][] memo new int[rows][cols]; int ret 0; for (int row 0; row rows; row) { for (int col 0; col cols; col) { ret Math.max(ret, dfs(matrix, row, col, memo)); } } return ret; } private int dfs(int[][] matrix, int row, int col, int[][] memo) { if (memo[row][col] ! 0) { return memo[row][col]; } int best 1; for (int[] direction : DIRECTIONS) { int nextRow row direction[0]; int nextCol col direction[1]; if (nextRow 0 || nextRow matrix.length || nextCol 0 || nextCol matrix[0].length || matrix[nextRow][nextCol] matrix[row][col]) { continue; } best Math.max(best, 1 dfs(matrix, nextRow, nextCol, memo)); } memo[row][col] best; return best; } }代码说明memo[row][col]保存从当前位置开始的最长递增路径长度。best从 1 开始因为当前格子本身已经算入路径。只有下一格严格大于当前格时才允许递归。由于每次移动都让数值变大不会在路径中形成循环缓存则避免不同起点反复计算同一个坐标的答案。六、从多道题中归纳记忆化搜索规律斐波那契的状态是一个数字n所以使用一维缓存。不同路径和矩阵最长递增路径的状态是坐标(row, col)所以使用二维缓存。最长递增子序列按起始下标记录状态猜数字 II 则把左右边界组成一个区间状态。这些题的共同流程可以固定为先写清dfs的状态定义再让memo的结构对应状态递归开始时先查询缓存如果没有计算过就根据更小状态得到答案计算完成后写回缓存。设计缓存时最重要的是判断状态是否完整。如果一个状态除了坐标还受到剩余步数影响就不能只用坐标作为缓存下标如果未来结果只与坐标有关就不需要把整条历史路径放进状态。还要区分“未计算”和“合法答案”。斐波那契可以用-1作为初始标记因为答案非负不同路径的答案可能为正所以可以用0表示未计算如果合法答案本身可能和初始值冲突可以使用Integer[][]和null。七、易错点memo没有包含完整状态导致不同状态错误共用一个答案。缓存查询放得太晚已经重复展开了递归。计算结果后忘记写回memo。合法答案可能是 0却直接用 0 作为未计算标记。把visited当成memo使用误以为访问过就代表答案已经算完。成员变量形式的缓存没有在公共方法开始时重新初始化。区间边界、数组下标或坐标定义不一致导致缓存位置与递归状态错位。八、本篇总结记忆化搜索的核心不是简单地多写一个数组而是找到“完全相同的状态”。递归负责描述状态如何转移memo负责保存每个状态的答案。无论状态是一维数字、二维坐标、数组下标还是区间只要状态定义完整、缓存初始化合理就能把重复计算从递归中消除。