这道题让我更深入的理解了记忆化搜索的过程，既然记忆化搜索的结果要靠返回值来传递，那么记忆化搜索解决问题的必须是倒序的，即记忆化搜索是一个简化问题倒序解决的过程，普通搜索是一个复杂化问题逐步尝试并记录尝试结果的过程。
特别是对于求总种数的记忆化搜索，就是把能干的事情组合起来然后把情况全都加到DFS变量中，然后直接return DP[*][*]=DFS即可。同时异常剪枝可以直接在递归搜索中进行。只进行常规的记忆化剪枝就可以。当然异常剪枝和搜索时判断边界同时来做，双重保险也是可以的。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
int N,M,DP[1005][1005],a[1005];
int dfs(int money,int considered_meal)//money is the rest money ;return_value is the count of how much way i can buy
{
//记忆化剪枝
if(DP[money][considered_meal]!=-1)return DP[money][considered_meal];
//cout<<money<<' '<<considered_meal<<endl;
//递归搜索，核心思想是求总种数就"能干啥干啥，不能就拉倒不用管"
int DFS=0;
//能干的事情的组合如下
//继承且买
if(money-a[considered_meal]>0&&considered_meal-1>0)DFS+=dfs(money-a[considered_meal],considered_meal-1);
//买但不继承
if(money-a[considered_meal]==0)DFS+=1;
//继承但不买
if(considered_meal-1>0)DFS+=dfs(money,considered_meal-1);
return DP[money][considered_meal]=DFS;
}
int main()
{
cin>>N>>M;
memset(DP,-1,sizeof(DP));DP[0][0]=0;
for(int i=1;i<=N;i++)
{
cin>>a[i];
}
cout<<dfs(M,N)<<endl;
return 0;
}