一、问题

二、思路

这道题其实看上去和我们的01背包问题是非常相似的。如果这道题我们转化为01背包问题的话，描述如下：
给很多个物品和体积，然后从中任取几个物品能够恰好填满背包的方案数。

1、状态表示

$f[i][j]$表示从$i$个物品里面选，经过选择后，总体积恰好为$j$的方案数。

2、状态转移

这道题既然能够转化为了背包问题，那么我们就可以尝试用背包问题中状态转移方程的书写思路解决这道题。
那么对于前i个物品而言，我们可以根据第i个物品是否选择来写转移方程，这样的话，我们就能够把问题规模从i减小为i-1。选或者选，总共两种情况，我们只需要把这两种情况加起来就可以算出总的方案数。

$$f(i,j)=\{\begin{array}{ll}f(i-1,j)& j<v[i]\\ f(i-1,j-v[i])+f(i-1,j)& j\ge v[i]\end{array}$$

3、循环设计

循环设计的话就很简单了，我们只需要将物品数量i作为外层循环即可，这样的话我们更加方便对其进行空间优化。

4、初末状态

初末状态对于这道题而言是非常关键的，因为对于之前的题目而言，我们求的是物品的价值，但是当背包容量是0的时候，我们没有选择任何物品，此时最大价值是0。也就是说，我们不需要初始化。

但是这道题不一样，这道题求的是方案数，如果我们的数字个数是0个，m又恰好等于0。此时我们从0个数中，选取几个数，使得这些数的总和恰好是0，这种方案数是1。

所以我们需要将f[0][0]初始化为1。

而题目中的恰好二字，就体现在$f[0][0]=1$这行代码。

三、代码

代码这里就写一个空间优化过后的代码吧。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110000;
int a[N],f[N];
int n,m;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",a+i);f[0]=1;for(int i=1;i<=n;i++)for(int j=m;j>=0;j--)if(j>=a[i])f[j]=f[j]+f[j-a[i]];cout<<f[m]<<endl;return 0;
}