2025力扣打卡系列动态规划从记忆化搜索到递推
目录
【2025力扣打卡系列】动态规划+从记忆化搜索到递推
坚持按题型打卡&刷&梳理力扣算法题系列，语言为python3，Day4
- 回溯三问
- 当前操作？枚举 第 i 个房子选/不选
- 子问题？从 前 i 个房子中得到的最大金额和
- 下一个子问题？分类讨论：
- 不选：从 前 i - 1个房子中得到的最大金额和
- 选：从 前 i -2 个房子中得到的最大金额和
- 没有将得到的金额作为递归的入参，而是作为返回值
- 记忆化搜索
- 递归搜索 + 保存计算结果 = 记忆化搜索
- 把递归的计算结果保存下来，那么下次递归到同样的入参时，就直接返回先前保存的结果
- @cache
- 原理：用一个hashmap来记录入参 和 对应的返回值
- 或者用数组来实现
- cache = [-1] * n
- 在dfs的过程中，if cache[I] != -1: return cache[I]（当前I对应的cache[I]对应的值不为-1时，就返回cache[I]保存的值）；在return res之前，将cache[I]中的值更新，即cache[I] = res
- 递归搜索 + 保存计算结果 = 记忆化搜索
打家劫舍
题目描述
在这里插入图片描述
代码参考
# 法一：直接用cache装饰器（击败100%）
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dfs(i):
if i < 0:
return 0
res = max(dfs(i-1),dfs(i-2)+nums[i])
return res
return dfs(n-1)
# 法二：单独开一个cache数组（击败3.55%）
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
cache = [-1] * n
def dfs(i):
if i < 0:
return 0
if cache[i] != -1:
return cache[i]
res = max(dfs(i-1),dfs(i-2)+nums[i])
cache[i] = res
return res
return dfs(n-1)- 升级版
- 自顶向下算：记忆化搜索
- 自底向上算：递推
- 1:1翻译成递推
- dfs——》f数组
- 递归——〉循环
- 递归边界——》数组初始值
# 法三
class Solution:
def rob(self, nums: List[int]) -> int:
n = 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] # f(n-1 +2) 因为整体全都+2了
# 空间优化
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
f0=f1=0
for i,x in enumerate(nums):
new_f = max(f1,f0 + x)
f0 = f1
f1 = new_f
return f1