记忆化搜索

记忆化搜索是什么？

• 定义: 在递归过程中把已算过的状态存起来, 再次遇到时直接返回缓存值;
• 存储: 用数组或哈希表按状态下标缓存子问题解;
• 本质: 自顶向下的动态规划, 与递推填表等价;

记忆化搜索和递推有什么区别？

维度	记忆化搜索	递推 dp
方向	自顶向下	自底向上
写法	递归 + 缓存	循环填表
可读性	更贴近问题定义	需要自行确定填表顺序
风险	递归过深会栈溢出	无栈溢出
局限	几乎不挑转移方程	复杂状态转移难以排出顺序

• 选择: 转移依赖关系不规则时优先记忆化搜索; 状态空间大且顺序清晰时优先递推;

记忆化搜索的解题步骤是什么？

• 第一步: 定义状态与状态转移方程 (同递推 dp);
• 第二步: 定义缓存容器, 记录"是否算过"和"算出的值";
• 第三步: 写递归函数, 入口先查缓存, 命中直接返回;
• 第四步: 递归返回前写入缓存, 再向上层返回;

const memo = new Map();
const dfs = (i) => {
  if (memo.has(i)) return memo.get(i);
  const value = transition(i); // 依赖 dfs(更小状态)
  memo.set(i, value);
  return value;
};

如何用记忆化搜索求矩阵中的最长递增路径？

• 问题: 在矩阵中从任意格出发, 每次只能走向严格更大的相邻格, 求最长路径长度 (329);
• 状态: memo[row][col] 为从该格出发的最长递增路径长度;
• 转移: 对四个方向中值更大的邻居取 1 + dfs(邻居) 的最大值;
• 初值: memo 全部填 1, 表示最短路径只有自身;
• 遍历: 枚举每个格子作为起点取最大值;

const longestIncreasingPath = (matrix) => {
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const m = matrix.length;
  const n = matrix[0].length;
  const memo = Array.from({ length: m }, () => new Array(n).fill(1));

  const dfs = (row, col) => {
    if (memo[row][col] !== 1) return memo[row][col];
    let max = 1;
    for (const [dx, dy] of dirs) {
      const r = row + dx;
      const c = col + dy;
      if (r < 0 || r >= m || c < 0 || c >= n) continue;
      if (matrix[r][c] <= matrix[row][col]) continue;
      max = Math.max(max, 1 + dfs(r, c));
    }
    memo[row][col] = max;
    return max;
  };

  let res = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) res = Math.max(res, dfs(i, j));
  }
  return res;
};

• 复杂度: 每个状态只被真正计算一次, 时间 O(mn), 空间 O(mn);