https://www.luogu.com.cn/problem/P1164
题目大意：
给定n种菜品（每种菜品只有1份），m块钱；
问我们花完了这m块钱可以点的不同种类的菜品有多少种方案数？
输入
4 4
1 1 2 2
输出
3
输入
10 9
1 2 3 4 5 6 7 8 9 10
输出
8
-
f[i][j]表示前i个菜品刚好花了j块钱的组合数
-
当只有0元的时候，买啥都买不起，所以边界状态就是1种：买不起的状态
状态转移的两种情况：
- 买当前第i道菜品，这个时候前i-1个菜品所需要的钱应该是j-a[i], 也就是说前i个物品中所有能凑出j-a[i]元的方案数量再加上当前这道菜品，就可以变成前i个物品所需的钱为j的方案数。
即f[i][j]+=f[i-1][j-a[i]]；
2.不买当前第i道菜品，这时候，也就是前i-1个物品凑成j的方案，
即f[i][j]+=f[i-1][j]；
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=200200,M=2002;
LL a[N];
LL f[M][M];
//f[i][j]表示前i个菜品刚好花了j块钱的组合数
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
LL n,m;
cin>>n>>m;
for(LL i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<=n;i++)
f[i][0]=1;
for(LL i=1;i<=n;i++)
{
for(LL j=1;j<=m;j++)
{
f[i][j]+=f[i-1][j];//默认不买，方案数和上一次达到j的方案数一样
if(j>=a[i]) f[i][j]+=f[i-1][j-a[i]];//买得起，再加上上一次刚好达到j-a[i]的数量
}
}
cout<<f[n][m]<<endl;
}
return 0;
}