推荐的一篇记忆化搜索文章

https://interestinglsy.blog.luogu.org/memdfs-and-dp

总结

记忆化搜索跟偏向于DP，使用数组来存储状态，当搜到搜过的位置时直接返回数组中记录的信息

十分高效的搜索方法

code

int DFS(int x){    if(dp[x]) return dp[x];  //记忆化搜索的核心，之前搜过直接返回，避免重复搜索    int ans=0; //开一个变量记录子树的答案    if(judge()) ans++;//符合条件更新ans    for(E in Edges)    {        ans+=DFS(E);//把子树答案上传     }     dp[x]=ans; return ans;//记忆化搜索核心，记录信息，再返回搜到的答案 }

例题   P3183 食物链

题目描述

如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

输入输出格式

输入格式：

第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）1<=N<=100000 0<=m<=200000题目保证答案不会爆 int

输出格式：

一个整数即食物网中的食物链条数

solution:

对于每个入度为0的点进行记忆化搜索，注意特判是否没有出度（即是否为孤立的生物）

当搜到一个点没有出度时就是食物链的末端

#include
     
      #include
      
       #define ll long long#define maxn 100050#define re register#define maxm 200050using namespace std;ll dp[maxn],ans;struct Edge{    int v,nxt;}e[maxm<<2];int x,y;int cnt,n,m,head[maxn],in[maxn],out[maxn];inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return f*x;}inline void add(int u,int v){    e[++cnt].v=v;    e[cnt].nxt=head[u];    head[u]=cnt;}ll dfs(int x){    if(dp[x]) return dp[x];    ll tmp=0;    if(!out[x]) ++tmp;    for(int i=head[x];i;i=e[i].nxt)    {        int v=e[i].v;        tmp+=dfs(v);    }    dp[x]=tmp; return tmp;}int main(){    n=read(); m=read();    for(re int i=1;i<=m;++i)    {        x=read();        y=read();        in[y]++;        out[x]++;        add(x,y);    }    for(re int i=1;i<=n;++i)    {        if(!in[i]&&out[i]) ans+=dfs(i);//别忘了特判    }    printf("%lld",ans);    return 0;}