01. 记忆化搜索知识
01. 记忆化搜索知识
1. 记忆化搜索简介
记忆化搜索(Memoization Search):是一种通过存储已经遍历过的状态信息,从而避免对同一状态重复遍历的搜索算法。
记忆化搜索是动态规划的一种实现方式。在记忆化搜索中,当算法需要计算某个子问题的结果时,它首先检查是否已经计算过该问题。如果已经计算过,则直接返回已经存储的结果;否则,计算该问题,并将结果存储下来以备将来使用。
举个例子,比如「斐波那契数列」的定义是:
从图中可以看出:如果使用普通递归算法,想要计算
为了避免重复计算,在递归的同时,我们可以使用一个缓存(数组或哈希表)来保存已经求解过的
使用「记忆化搜索」方法解决斐波那契数列的代码如下:
class Solution:
def fib(self, n: int) -> int:
# 使用数组保存已经求解过的 f(k) 的结果
memo = [0 for _ in range(n + 1)]
return self.my_fib(n, memo)
def my_fib(self, n: int, memo: List[int]) -> int:
if n == 0:
return 0
if n == 1:
return 1
# 已经计算过结果
if memo[n] != 0:
return memo[n]
# 没有计算过结果
memo[n] = self.my_fib(n - 1, memo) + self.my_fib(n - 2, memo)
return memo[n]
2. 记忆化搜索与递推区别
「记忆化搜索」与「递推」都是动态规划的实现方式,但是两者之间有一些区别。
记忆化搜索:「自顶向下」的解决问题,采用自然的递归方式编写过程,在过程中会保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。
- 优点:代码清晰易懂,可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的,使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题,通过递归调用来解决。
- 缺点:可能会因为递归深度过大而导致栈溢出问题。
递推:「自底向上」的解决问题,采用循环的方式编写过程,在过程中通过保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。
- 优点:避免了深度过大问题,不存在栈溢出问题。计算顺序比较明确,易于实现。
- 缺点:无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂,如果使用递推方法来计算,就会导致代码实现变得非常困难。
根据记忆化搜索和递推的优缺点,我们可以在不同场景下使用这两种方法。
适合使用「记忆化搜索」的场景:
- 问题的状态转移方程比较复杂,递推关系不是很明确。
- 问题适合转换为递归形式,并且递归深度不会太深。
适合使用「递推」的场景:
- 问题的状态转移方程比较简单,递归关系比较明确。
- 问题不太适合转换为递归形式,或者递归深度过大容易导致栈溢出。
3. 记忆化搜索解题步骤
我们在使用记忆化搜索解决问题的时候,其基本步骤如下:
- 写出问题的动态规划「状态」和「状态转移方程」。
- 定义一个缓存(数组或哈希表),用于保存子问题的解。
- 定义一个递归函数,用于解决问题。在递归函数中,首先检查缓存中是否已经存在需要计算的结果,如果存在则直接返回结果,否则进行计算,并将结果存储到缓存中,再返回结果。
- 在主函数中,调用递归函数并返回结果。
4. 记忆化搜索的应用
4.1 目标和
4.1.1 题目链接
4.1.2 题目大意
描述:给定一个整数数组 +
或 -
。然后串联起来构造成一个表达式。
要求:返回通过上述方法构造的、运算结果等于
说明:
。 。 。 。
示例:
- 示例 1:
输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
- 示例 2:
输入:nums = [1], target = 1
输出:1
4.1.3 解题思路
思路 1:深度优先搜索(超时)
使用深度优先搜索对每位数字进行 +
或者 -
,具体步骤如下:
- 定义从位置
、和为 开始,到达数组尾部位置为止,和为 的方案数为dfs(0, 0)
。 - 下面从位置
、和为 开始,以深度优先搜索遍历每个位置。 - 如果当前位置
到达最后一个位置 :- 如果和
等于目标和 ,则返回方案数 。 - 如果和
不等于目标和 ,则返回方案数 。
- 如果和
- 递归搜索
位置,和为 的方案数。 - 递归搜索
位置,和为 的方案数。 - 将 4 ~ 5 两个方案数加起来就是当前位置
、和为 的方案数,返回该方案数。 - 最终方案数为
dfs(0, 0)
,将其作为答案返回即可。
思路 1:代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
size = len(nums)
def dfs(i, cur_sum):
if i == size:
if cur_sum == target:
return 1
else:
return 0
ans = dfs(i + 1, cur_sum - nums[i]) + dfs(i + 1, cur_sum + nums[i])
return ans
return dfs(0, 0)
思路 1:复杂度分析
- 时间复杂度:
。其中 为数组 的长度。 - 空间复杂度:
。递归调用的栈空间深度不超过 。
思路 2:记忆化搜索
在思路 1 中我们单独使用深度优先搜索对每位数字进行 +
或者 -
的方法超时了。所以我们考虑使用记忆化搜索的方式,避免进行重复搜索。
这里我们使用哈希表
- 定义从位置
、和为 开始,到达数组尾部位置为止,和为 的方案数为dfs(0, 0)
。 - 下面从位置
、和为 开始,以深度优先搜索遍历每个位置。 - 如果当前位置
遍历完所有位置:- 如果和
等于目标和 ,则返回方案数 。 - 如果和
不等于目标和 ,则返回方案数 。
- 如果和
- 如果当前位置
、和为 之前记录过(即使用 记录过对应方案数),则返回该方案数。 - 如果当前位置
、和为 之前没有记录过,则:- 递归搜索
位置,和为 的方案数。 - 递归搜索
位置,和为 的方案数。 - 将上述两个方案数加起来就是当前位置
、和为 的方案数,将其记录到哈希表 中,并返回该方案数。
- 递归搜索
- 最终方案数为
dfs(0, 0)
,将其作为答案返回即可。
思路 2:代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
size = len(nums)
table = dict()
def dfs(i, cur_sum):
if i == size:
if cur_sum == target:
return 1
else:
return 0
if (i, cur_sum) in table:
return table[(i, cur_sum)]
cnt = dfs(i + 1, cur_sum - nums[i]) + dfs(i + 1, cur_sum + nums[i])
table[(i, cur_sum)] = cnt
return cnt
return dfs(0, 0)
思路 2:复杂度分析
- 时间复杂度:
。其中 为数组 的长度。 - 空间复杂度:
。递归调用的栈空间深度不超过 。
4.2 第 N 个泰波那契数
4.2.1 题目链接
4.2.2 题目大意
描述:给定一个整数
要求:返回第
说明:
- 泰波那契数:
,且在 的条件下, 。 。- 答案保证是一个 32 位整数,即
。
示例:
- 示例 1:
输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
- 示例 2:
输入:n = 25
输出:1389537
4.2.3 解题思路
思路 1:记忆化搜索
- 问题的状态定义为:第
个泰波那契数。其状态转移方程为: ,且在 的条件下, 。 - 定义一个长度为
数组 用于保存一斤个计算过的泰波那契数。 - 定义递归函数
my_tribonacci(n, memo)
。- 当
或者 ,或者 时直接返回结果。 - 当
时,首先检查是否计算过 ,即判断 是否等于 。- 如果
,说明已经计算过 ,直接返回 。 - 如果
,说明没有计算过 ,则递归调用my_tribonacci(n - 3, memo)
、my_tribonacci(n - 2, memo)
、my_tribonacci(n - 1, memo)
,并将计算结果存入 中,并返回 。
- 如果
- 当
思路 1:代码
class Solution:
def tribonacci(self, n: int) -> int:
# 使用数组保存已经求解过的 T(k) 的结果
memo = [0 for _ in range(n + 1)]
return self.my_tribonacci(n, memo)
def my_tribonacci(self, n: int, memo: List[int]) -> int:
if n == 0:
return 0
if n == 1 or n == 2:
return 1
if memo[n] != 0:
return memo[n]
memo[n] = self.my_tribonacci(n - 3, memo) + self.my_tribonacci(n - 2, memo) + self.my_tribonacci(n - 1, memo)
return memo[n]
思路 1:复杂度分析
- 时间复杂度:
。 - 空间复杂度:
。
参考资料
- 【文章】记忆化搜索 - OI Wiki
来源:https://github.com/itcharge/LeetCode-Py