本题为完全背包求方案数:f[i][j]表示前i个且方案数总和为j的方案数,同时可以优化为一维
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=10010;
int n,m;
LL f[N];
int main(){
cin>>n>>m;
f[0]=1;//什么都不选方案数为1
for(int i=0;i<n;i++){
int v;
cin>>v;
for(int j=v;j<=m;j++){
f[j]+=f[j-v];
}
}
cout<<f[m]<<endl;
return 0;
}