记忆化回溯搜索-@cache --＞ 动态规划
目录
DFS回溯 + 记忆化
首先我们确定回溯三问（参考灵神）
接着通过上面的回溯三问实现基础的DFS
最后加入记忆化
@cache
存储
动态规划
翻译翻译
用滚动优化空间负责度
注：本文以动态规划入门：从记忆化搜索到递推【基础算法精讲 17】_哔哩哔哩_bilibili为基础
动态规划一般是递推填表，DFS回溯 + 记忆化是从后往前，他们的本质是一样的
DFS回溯 + 记忆化
什么是记忆化？记下干过的事情的结果，那么下次还需要干这件事情时，直接调取上一次干这件事的结果就好
当解决的问题有重叠子问题特征时，在正常的DFS中肯定会有算力浪费在类似问题上，那么我们就可以用上记忆化
像这颗搜索树中圈起来的部分是重复的
下面介绍一下基本思路：
首先我们确定回溯三问（参考灵神）
因为我们的问题有重叠子问题的特征，所以我们可以用类似于数学归纳法
1. 当前怎么操作？ i
2. 子问题怎么操作？ i-1
3. 下一个子问题怎么操作？ i-2
接着通过上面的回溯三问实现基础的DFS
确定边界条件（也就是搜索树的叶子节点）后，根据回溯关系实现搜索
以198.打家劫舍为例子
上面那张图就是198的搜索树，注意：不选的也算在树里面，而不是直接空着的，这样看起来更有逻辑性，
class Solution:def rob(self, nums: List[int]) -> int:l=len(nums)def dfs(i):#到第i时候的最大值（也就是题目要求的值）if i<0:return 0res=max(dfs(i-1),dfs(i-2)+nums[i])#不要i 要ireturn resreturn dfs(l-1)最后加入记忆化
@cache
在py中我们可以用
@cache来装饰一个函数，Python 会自动记住这个函数之前的输入和输出。下次调用这个函数时，如果传入的参数和以前一样，就直接返回上次的结果，而不是重新计算。（黑箱）
请注意： @cache 必须写在对应函数的 def 的上一行，这是 Python 中装饰器的固定语法格式。
使用前记得先导入
from functools import cache那么这道题我们加入记忆化就是（参考灵神）
from functools import cacheclass Solution:def rob(self, nums) :l=len(nums)@cachedef dfs(i):#到第i时候的最大值（也就是题目要求的值）if i<0:return 0res=max(dfs(i-1),dfs(i-2)+nums[i])#不要i 要ireturn resreturn dfs(l-1)存储
我们也可以用存储，那么途径就很多了，比如数组、字典等等
动态规划
翻译翻译
1. dfs -> f数组
2. 递归 -> 循环
3. 递归边界 -> 初始值
那么我们的198就是
class Solution:def rob(self, nums) :l=len(nums)f=[0]*(n+2)for i,x in enumerate(nums):f[i+2]=max(f[i+1],f[i]+x)return f[n+1]用 for i,x in enumerate(nums): 比 for i in range(n):nums[i] 能凹一些时间
用滚动优化空间负责度
从 f[i+2]=max(f[i+1],f[i]+x) 可以归纳：我们第 i+2 个只需要第 i+1 个和第 i 个，那么我们只需要创造两个位置让他们滚动起来互相帮助填充就好
class Solution:def rob(self, nums) :l=len(nums)#f=[0]*(n+2)f0=f1=0#for i,x in enumerate(nums):#f[i+2]=max(f[i+1],f[i]+x)for x in nums:newf=max(f1,f0+x)f0=f1f1=newfreturn f1