@[大Y杨](/space/show?uid=149325) 记忆化搜索
by PRXOR @ 2019-02-19 11:55:01
记忆化记忆化。。。
by PZimba @ 2019-02-19 12:06:46
得记忆化吧，要不TLE正常
by yizimi远欣 @ 2019-02-19 12:28:03
@[大Y杨](/space/show?uid=149325)
by yizimi远欣 @ 2019-02-19 12:28:20
记忆化就好了~
by Createsj @ 2019-02-19 12:32:40
$\mathcal{My~Code}$
```cpp
int fun(long long int a,long long int b,long long int c)
{
if(a<=0 || b<=0 || c<=0)
return 1;
else if(a>20 || b>20 || c>20)
return 1048576;
else if(a<b && b<c)
return f[a][b][c]?f[a][b][c]:(f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c));
else
return f[a][b][c]?f[a][b][c]:(f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1));
}
```
by Createsj @ 2019-02-19 12:33:41
DP也可以
by 塔罗兰 @ 2019-02-19 12:36:20
> ## 说明
记忆化搜索
说明里都写的清清楚楚了，不写记忆化肯定超时啊
by NaCly_Fish @ 2019-02-19 12:36:59
加一个数据处理
by 塔罗兰 @ 2019-02-19 12:37:39
记忆化搜索/递归式动态规划：
1.记忆化搜索的思想
记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量
2、记忆化搜索的适用范围
根据记忆化搜索的思想，它是解决重复计算，而不是重复生成，也就是说，这些搜索必须是在搜索扩展路径的过程中分步计算的题目，也就是“搜索答案与路径相关”的题目，而不能是搜索一个路径之后才能进行计算的题目，必须要分步计算，并且搜索过程中，一个搜索结果必须可以建立在同类型问题的结果上，也就是类似于动态规划解决的那种。
也就是说，他的问题表达，不是单纯生成一个走步方案，而是生成一个走步方案的代价等，而且每走一步，在搜索树/图中生成一个新状态，都可以精确计算出到此为止的费用，也就是，可以分步计算，这样才可以套用已经得到的答案
3、记忆化搜索的核心实现
a. 首先，要通过一个表记录已经存储下的搜索结果，一般用哈希表实现
b.状态表示，由于是要用哈希表实现，所以状态最好可以用数字表示，常用的方法是把一个状态连写成一个p进制数字，然后把这个数字对应的十进制数字作为状态
c.在每一状态搜索的开始，高效的使用哈希表搜索这个状态是否出现过，如果已经做过，直接调用答案，回溯
d.如果没有，则按正常方法搜索
4、记忆化搜索是类似于动态规划的，不同的是，它是倒做的“递归式动态规划”。
原贴：https://blog.csdn.net/Acmer_Sly/article/details/53440798
by 大Y杨 @ 2019-02-19 13:43:13