Q1 198. 打家劫舍
解法一：
知识点：记忆化搜索=递归搜索+保留计算结果
递归部分：
这样写能够完成上述题目，但是会超时，因为时间复杂度是质数级别，这时候就需要改进代码，也就是保留结果
Cache
简单解释一下，这里就运用了cache，起初全设置为-1，在进入dfs函数之后首先我们会判断这个dfs之前有没有调用过，也就是有没有保存过计算后的值，如果有，那么直接用，如果没有责在res计算后将其数值记到cache中，以便后续使用，这时候时间，空间复杂度都是n
修改后的代码：
此时复杂度还是n
优化：
升级版（记忆化搜索
代码：
优化：首先进入dfs之前就将三种方式都计算一遍，将得到的target值作为参数传入dfs
解释一下res=max（res，dfs（xxx）+1）,为什么要把res和后面的对比来选择最大的，我们知道三个if是顺序执行的，在第二个if执行的时候，res的值已经是第一轮if执行完更新后的res了，所以第二个if中的res其实是第一个if执行完成后的if，相对的，第三个if中的res其实是第二个if执行完的if，那么为什么第一个if也要加res=max（res，dfs（xxx）+1）呢？，因为第一个if也要进入dfs的三个if，同样要通过比较三个if的res来筛选出最大的res
标签：res,复杂度,cache,dfs,记忆,搜索,执行 From： https://blog.csdn.net/2301_78295022/article/details/139564912