记忆化搜索type
status
date
slug
summary
tags
category
icon
password
Property
记忆化搜索（Memoization Search）：是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。
记忆化搜索是动态规划的一种实现方式。在记忆化搜索中，当算法需要计算某个子问题的结果时，它首先检查是否已经计算过该问题。如果已经计算过，则直接返回已经存储的结果；否则，计算该问题，并将结果存储下来以备将来使用。
为了避免重复计算，在递归的同时，我们可以使用一个缓存（数组或哈希表）来保存已经求解过的的结果。当递归调用用到时，先查看一下之前是否已经计算过结果，如果已经计算过，则直接从缓存中取值返回，而不用再递推下去，这样就避免了重复计算问题。
记忆化搜索与递推区别
「记忆化搜索」与「递推」都是动态规划的实现方式，但是两者之间有一些区别。
记忆化搜索：「自顶向下」的解决问题，采用自然的递归方式编写过程，在过程中会保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
- 优点：代码清晰易懂，可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的，使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题，通过递归调用来解决。
- 缺点：可能会因为递归深度过大而导致栈溢出问题。
递推：「自底向上」的解决问题，采用循环的方式编写过程，在过程中通过保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
- 优点：避免了深度过大问题，不存在栈溢出问题。计算顺序比较明确，易于实现。
- 缺点：无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂，如果使用递推方法来计算，就会导致代码实现变得非常困难。
根据记忆化搜索和递推的优缺点，我们可以在不同场景下使用这两种方法。
适合使用「记忆化搜索」的场景：
- 问题的状态转移方程比较复杂，递推关系不是很明确。
- 问题适合转换为递归形式，并且递归深度不会太深。
适合使用「递推」的场景：
- 问题的状态转移方程比较简单，递归关系比较明确。
- 问题不太适合转换为递归形式，或者递归深度过大容易导致栈溢出。
记忆化搜索解题步骤
使用记忆化搜索解决问题的时候，其基本步骤如下：
- 写出问题的动态规划「状态」和「状态转移方程」。
- 定义一个缓存（数组或哈希表），用于保存子问题的解。
- 定义一个递归函数，用于解决问题。在递归函数中，首先检查缓存中是否已经存在需要计算的结果，如果存在则直接返回结果，否则进行计算，并将结果存储到缓存中，再返回结果。
- 在主函数中，调用递归函数并返回结果。
矩阵中的最长递增路径
题目：给定一个
m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。对于每个单元格，可以往上，下，左，右四个方向移动。 不能在对角线方向上移动或移动到 边界外（即不允许环绕）。示例：
