优化暴力递归
递归层数太深会超时+栈溢出
对策
- 记忆化递归
- 剪枝
int f(int x){if(x==1||x==2)return 1;return f(x-1)+f(x-2);
}
记忆化
int F[101]={-1};
int f(int x){if(x==1||x==2)return 1;if(F[x]!=-1)return F[x];return F[x]=f(x-1)+f(x-2);
}
例题
luogu P1464
经典记忆化递归题目
ll A,B,C;
ll m[30][30][30];
ll w(ll a,ll b,ll c){if(a<=0||b<=0||c<=0)return 1;if(a>20||b>20||c>20)return w(20,20,20);if(m[a][b][c]!=-1)return m[a][b][c];if(a<b&&b<c)return m[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);return m[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);
}
void solve(){memset(m,-1,sizeof(m));while(cin>>A>>B>>C){if(A==-1&&C==-1&&B==-1)return;cout<<"w("<<A<<", "<<B<<", "<<C<<") = "<<w(A,B,C)<<'\n';}
}
luogu P1164
正解是dp,不过暴力递归遍历+记忆化+剪枝也是ac了
int ans=0;
int n,m;
int a[101],f[101][10005];
void dfs(int sum,int indx){if(f[indx][m-sum]){ans+=f[indx][m-sum];return;}if(sum==m){ans++;return;}if(sum>m)return;int t=ans;for(int i=indx;i<n;++i){dfs(sum+a[i],i+1);}f[indx][m-sum]=ans-t;
}
void solve(){read(n,m);for(int i=0;i<n;++i)read(a[i]);memset(f,0,sizeof(f));dfs(0,0);wr(ans);
}