题目:小A点菜
首先是普通搜索，分为选和不选
代码如下:

#include<iostream>
using namespace std;
int n,m;
int a[105];
long long ans;
void dfs(int i,int p)//当前点到多少个菜，剩余多少钱 
{
	if(p==0)
	{
	ans++;
	return;
}
	if(i>n)return;
	if(p<0)return;
	if(p-a[i+1]>=0)
	{
		dfs(i+1,p-a[i+1]);
	}
	dfs(i+1,p);
 } 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	dfs(0,m);
	cout<<ans<<endl;
	return 0; 
 }   

这样写90分，最后一个点TLE
然后改为某种形式的记忆化搜索（这里称之为形式1）
代码如下：

using namespace std;
int a[105];
int f[105][100005];
long long ans;
int n,m; 
int dfs(int i,int c)//当前要买的编号 有的money 
{
   if(f[i][c])return f[i][c];
   if(c-a[i]==0)return 1;
   if(i>n||c-a[i]<0)return 0;
   for(int k=i+1;k<=n;k++)
   f[i][c]+=dfs(k,c-a[i]);
   return f[i][c];
}
int main()
{
   cin>>n>>m;
   for(int i=1;i<=n;i++)
   cin>>a[i];
   for(int i=1;i<=n;i++)
   ans+=dfs(i,m); 
   cout<<ans<<endl;
   return 0;

}   

这种递归过程中的搜索树并不是二叉树

然后我就想着把一开始的纯搜索改成记忆化搜索，这时候还是分为某个节点选和不选，搜索树是二叉树的形式 （形式2） 代码如下：

#include<iostream>
using namespace std;
int n,m;
int a[105];
int f[105][10005];
long long ans;
int dfs(int i,int k)
{
	if(f[i][k])return f[i][k];
	if(i>n)return 0;
	if(k-a[i]==0)f[i][k]+=1;//当前有就记录下来，继续搜 
	f[i][k]+=dfs(i+1,k-a[i]);
	f[i][k]+=dfs(i+1,k);
	return f[i][k];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	ans=dfs(1,m);
	cout<<ans<<endl;
	return 0;
}  

结果是:原先纯搜索的超时最后一个点（第11个测试点）2ms过了，然后6 7 8 9 10 超时55分，反而比春搜索还低分，于是困惑不解