记忆化搜索（搜索+dp思想）

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一：简介

（1）记忆化搜索 即 搜索+动态规划数组记录上一层计算结果，避免过多的重复计算

算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存；一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。
这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。可以归纳为：记忆化搜索=搜索的形式+动态规划的思想

（2）简单例子

题目描述：已知n个slots，1<n<17，每个slot有一个height，height的值有四种，分别为{1,2,3,4}.给你n个slot的，必须满足以下两个条件，求有多少种情况.  一：必须有两个相邻的slot的差为3，即一个为4，一个为1.    二：必须有三种不同的height值.
Sample Input
2
3
-1
Sample Output
2: 0
3: 8
这道题有组合公式，但想推出来不容易，其实用搜索就能很好地解决。
如果用暴搜的话，当n>10就会超时。这时，很容易想到动态规划，但DP不仅需要推出状态转移方程式，还要进行拓扑排序，对于这题，很难用传统的DP解决。虽然不能使用传统意义上的动态规划解决本题，但动态规划的思想仍然能起到作用。搜索相对于动态规划最大的劣势无非就是重复计算子结构，所以我们在搜索的过程中，对于每一个子结构只计算一次，之后保存到数组里，以后要用到的时候直接调用就可以了，这就是我要介绍的记忆化搜索。
记忆化搜索的实质是动态规划,效率也和动态规划接近，形式是搜索,简单直观，代码也容易编写，不需要进行什么拓扑排序了。
对于状态的存储，可用数组num[a] [b][c][d]，其中a为还剩几个，b为找到了哪几个，c为找到的最后一个数，d表示是否已经出现1，4相连的两数

二：案例详解

（1）题目描述：给从左至右排好队的小朋友们分糖果，
要求：1.每个小朋友都有一个得分，任意两个相邻的小朋友，得分较高的所得的糖果必须大于得分较低的，相等则不作要求。
       2.每个小朋友至少获得一个糖果。

求：至少需要的糖果数。
输入：
输入包含多组测试数据，每组测试数据由一个整数n（1<=n<=100000）开头，接下去一行包含n个整数，代表每个小朋友的分数Si（1<=Si<=10000）。
输出：
对于每组测试数据，输出一个整数，代表至少需要的糖果数。

（2）解题报告

所有人的最小能分配到的糖果值就可以通过他的左右两个人计算出来。可以采用记忆化搜索算法。复杂度是O(n)；

input:
3
1 10 1
3
6 2 3
2
1 1
output:
4
5
2

（3）代码实现

#include<cstdio>
#include<cstring>
#define MAX 100001
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;

int cal(int r,int n,int dp[],int Arr[])
{
    if(dp[r]>0)
        return dp[r];//已经计算过
    dp[r]=1;
    if(r+1<=n&&Arr[r]>Arr[r+1])//右边有人比他小，要受右边限制
        dp[r]=max(dp[r],cal(r+1,n,dp,Arr)+1);
    if(r-1>=1&&Arr[r]>Arr[r-1])//左边有人比他小，要受左边限制
        dp[r]=max(dp[r],cal(r-1,n,dp,Arr)+1);
    return dp[r];
}

int main(int argc,char *argv[])
{
    int n;
    int Arr[MAX];
    int dp[MAX];
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            scanf("%d",&Arr[i]);
        long long sum=0;
        for(i=1;i<=n;i++)
            sum+=cal(i,n,dp,Arr);
        printf("%lld\n",sum);
    }

    return 0;
}