一：简介
（1）记忆化搜索 即 搜索+动态规划数组记录上一层计算结果，避免过多的重复计算
算法上仍然是检索的流程，但检索到的一些解以动态修订的思想和模式存储； 通常，动态规划需要始终遍历所有状态，但搜索可以排除一些无效状态。 更重要的是，搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多
记忆算法求解时还是自上而下的顺序，但每次求解一个状态时保存其解。 http://www.Sina.com/http://www.Sina.com /
以后再次遇到这个状态的时候，就不必重新求解了
主题：已知有n个slots，1n17。 每个slot有一个高。 height的值有4种，分别为{ 1、2、3、4 }。 给n个slot的时候，必须满足以下两个条件，必须求出有多少情况。 1 :相邻的两个slot之间的差必须为3
样本输入
2
3
-1
样本输出
2: 0
3: 8
这个问题有组合式，但出起来并不容易。 其实搜索可以很好地解决。
用强暴搜索的话，到了n10就会超时。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。可以归纳为：记忆化搜索=搜索的形式+动态规划的思想动态规划的搜索最大缺点就是重复计算子结构，所以在搜索过程中，每个子结构只计算一次，然后存储在数组中，以后使用时直接调用即可。 这就是我要介绍的记忆化搜索。
记忆化检索的本质是动态规划，效率也接近动态规划，形式是检索，简单直观，代码也容易编写，不需要拓扑排序。
数组num[a] [b][c][d]可用于存储状态。 其中a表示剩下的数量，b表示找到的数量，c表示找到的最后一个数量，d表示1，4是否已经连接
（2）简单例子
)1)主题说明)把糖果分给从左到右排列的孩子们，
要求：1.所有孩子都有一个得分，任何两个旁边的孩子，得分高的糖果必须大于得分低的，相等的不要求。
2 .每个孩子至少得到一个糖果。
要求：至少需要的糖果数量。
输入：
输入多个测试数据。 每个测试数据以整数n(1=n=100000 )开始，下一行包含n个整数，表示每个孩子的分数si(1=si=10000 )。
输出：
对于每组测试数据，输出一个整数，至少表示所需的糖果数。
)2)解题报告
分配给所有人最小的糖果值可以由他左右两个人来计算。 可以采用记忆化检索算法。 复杂度为o(n )；
input :31101362321 output :452 (3)代码实现
# include cstdio # include cstring # definemax 100001 # definemax (a，b ) (a ) ) b )？ (a ) 3360 ) b )使用命名空间STD； intcal(intr，int n，int dp[]，int Arr[] ) if ) DP[r]0) return dp[r]； 计算dp[r]=1的if(r1=nArr[r]arr[r1] ) /右边有比他小的人，右边限制dp[r]=max(DP[r]，cal(r1，n，DP，arr ) ) if(r-1=1Arr(r ) Arr (r ) r-1 ) ) /左边有人比他小，左边有dp(r )=max (dp ) r ) )、cal(r-1，n，DP，arr ) ) 1； 返回DP [ r ]； }intmain(intargc，char *argv[] ) { int n； int Arr[MAX]； int dp[MAX]； wile (扫描(' % d '，n )！=eof({intI； 短信(DP，0，sizeof ) DP )； for(I=1； i=n； I ) Scanf('%d”，Arr[i]； 龙龙三星=0； for(I=1； i=n； I ) sum=cal(I，n，dp，Arr )； printf(%lld(n )，sum )； }返回0； }