1.记忆化搜索
记忆化搜索就是搜索过程中记下搜索的值 很简单 没什么好说的
下面是一个简单的斐波拉契数列的记忆化搜索代码
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define N 100000 using namespace std; int f[N]; int dfs(int x){ if(f[x]) return f[x]; else return dfs(x-2)+dfs(x-1); } int main(){ f[1]=1;f[2]=1; int n; scanf("%d",&n); printf("%d",dfs(n)); return 0; }2.记忆化搜索+hash优化
每次计算f[x],如果x太大 达到了10^9 f数组就开不了 这个时候就用hash优化
将f[x]的值存到f[x%M]中 M为类似100017或者10017的大质数
但是 如果这个值冲突怎么办 当然会有多个x%M相等
这个时候邻接表就可以解决问题了 在结构体中开3个域 1.x%M 2.x（查找的时候用）3.答案
详细见 vijos1599 货币解法 后面一篇博客中 传送
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<malloc.h> #define M 10017 #define ll long long using namespace std; struct node{ int s; ll v; struct node *next; }*a[M]; ll dfs(ll x){ struct node *p; p=a[x%M]; while(p!=NULL){ int k=p->s; if(k==x) return p->v; p=p->next; } ll ans; if(x<=11) ans=x; else { ll t=dfs(x/2)+dfs(x/3)+dfs(x/4); if(x<t) ans=t;else ans=x; } struct node *q; q=(struct node*)malloc(sizeof(struct node)); q->s=x; q->v=ans; q->next=a[x%M]; a[x%M]=q; return ans; } int main(){ int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); printf("%lld\n",dfs(n)); } return 0; }
3.树形dp
f 数组记下来状态所对应的答案 就行了
对于每个状态考虑 可以得到的答案一层层推出最终答案
树形dp 就是树上的dp了 也是树上的记忆化搜索 （说了等于白说） 核心就是对于一个树 考虑它和它子树的情况 分情况取值 比如f[i][j]可以 表示i号顶点 在j状态的的最什么值
例题 tvyj1051
// http://www.tyvj.cn/p/1051 //树形dp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 500 using namespace std; int n,m; struct node{ int left,right,data; }a[N]; int son[N],f[N][N]; int dfs(int x,int num){ if(f[x][num]) return f[x][num]; if(x==0||num==0) return f[x][num]=0; int t=0; t=max(t,dfs(a[x].right,num));//不走根只走右 t=max(t,dfs(a[x].left,num-1)+a[x].data);//走根和左 左节点的先修课一定是他的跟 但是右结点不是 因为是孩子兄弟表示法 t=max(t,dfs(a[x].right,num-1)+a[x].data);//走根也走右 for(int k=1;k<=num-2;k++)//若果这里写k=0到num-1 上面两行不用写 t=max(t,dfs(a[x].left,k)+dfs(a[x].right,num-k-1)+a[x].data); // printf("f[%d][%d]=%d\n",x,num,t); return f[x][num]=t; } int main(){ scanf("%d%d",&n,&m); int x,y; for(int i=1;i<=n;i++){//树转二叉树 scanf("%d%d",&x,&y); a[i].data=y; if(a[x].left==0) a[x].left=i; else a[son[x]].right=i; son[x]=i; } printf("%d",dfs(a[0].left,m)); return 0; }
