DFS 记忆化 - wenzhoullq/leetcode GitHub Wiki
分析
记忆化dfs等同于dp,因此将它从回溯中取走；它通过建立一个coach数组来记忆化存储，减少回溯的次数，降低时间复杂度;值得注意的是，这种记忆化的coach是只在乎后续内容，至于前面的内容如何是不会加入到coach中的，并且前面的内容不会影响后续dfs，因此在dfs的过程中，很多都是**空值(如0,new )**去当参数。
重要点在于coach的构造，可能涉及压缩算法，可能涉及字符串的拼接，可能涉及三维(三维主要和dp的类型有关)，以及dfs的类型的判断，是长度型，存在型还是数量型，其中coach和dfs是一个类型的,而dfs和主函数是一个类型；
dfs简单易懂，但是记忆化dfs有个致命的弱点：当n>=1e9时且存在三个dfs会超时，因此需要化作动态规划的形式或则将一个dfs()优化掉
对于树形DP的记忆化,需要一个map储存root节点
分类
题目可以从两个角度进行分类，一个是从返回值的类型来分类，另一种是从dp的种类来分类
数量型
模板
coach=-1;//这里需要注意的是，有可能遇到不满足的情况，因此需要初始化为-1；
int dfs(){
//如果coach被访问过，返回访问值
if(到末端){
if(满足) return 1;
return 0;
}
int temp=0;//为什么设置temp=0来求，因为可能存在服务不满足的情况
for(){
if(不满足) continue;//这里的不满足和上面的不满足两者取其一，如何选择呢？一般来说，如果涉及到前值得比较，那么在这里比较；如果是不涉及，一般选择上方
temp+=dfs();
}
dp[i]=temp ;//
主要是判断何时满足才能方案数+1，这个是重点.
return dp[i];
}
题目
- 费用型
638. 大礼包 全是自买和全是礼包之间的抉择
- 方案数型
LCP 64. 二叉树灯饰树形DP,同时还有打开多个的操作
[NOIP2008]传球游戏 (用dp更快)
存在型
题目
长度型
模板
一般用于最大/最长用这个模板,如果是最短/最小的话以bfs居多,非要用记忆化DFS的话,则是记录step+1慢慢剪枝
int dfs(int index){
//如果coach被访问过，返回访问值
//如果到边缘，边缘处理
int sum=1;
for(int i=index,i<len;i++)
sum=Math.max(dfs()+1,sum);//长度型的精髓在于这个+1
//coach赋值
return sum;
}
题目
- 最大/长
1553. 吃掉 N 个橘子的最少天数 这题非常坑，第一个坑是如果按照模板来，空间复杂度会超时，因此需要简化dfs(n-1)+1部分，而这个简化是含有贪心思想；第二个坑是int[]的长度范围，需要用HashMap替代
- 最小/短
字符串型
题目
三个dfs会超时
要么想办法优化掉一个dfs，要么用dp
题目
dp角度
从dp角度分类记忆化dfs
状压dp
题目
区间dp
区间DP分为1维区间和2维区间;另外一种是取后对原排列有影响的，此时又是另一种构建方法
模板
int dfs(int left,int right){
//如果coach被访问过，返回访问值
//如果到边缘，边缘处理
int sum=0;
for(int i=left,i<=right;i++){
sum=Math.max(sum,nums[i]+dfs(left,i-1)+dfs(i+1,right));
}
//coach赋值
return sum;
}
题目
- 取后无影响
241. 为运算表达式设计优先级 用list代替第三维
486. 预测赢家 跟首尾取牌的某题有点像，但是是两个人的取值，并且只能取首尾（如果不是限定取首尾则是全排列），因此用区间DP,并且同2267，采用的是相对分数
877. 石子游戏 同486
894. 所有可能的满二叉树 树状区间DP
1444. 切披萨的方案数(表面上是二维，实质上还是一维)
- 取后有影响
312. 戳气球 戳气球的构造方法比较有意思，因为戳后有影响，它不是自底向上一个个戳的，而是自底向上一个个添加的
546. 移除盒子 这种是一系列题目，都是连成排的，并且取后有影响的，因此第三位是j后面有多少个相同的，还有个点是k和r的变化与coach的关系
664. 奇怪的打印机 同546，需要思考的一点是，改变颜色跟直接消除是等价的