数字组合

本题求解的是N个数中，有多少种组合可以实现其中一部分数字的和为M

本题的动态转移数组f[i,j]表示的是前i个数之和为j的方案总数

面临第i个数的时候，有选和不选两种操作：
1.若选，则其的总数为前i-1个数和为j-v[i]的方案数，其f[i][j] = f[i-1][j-v[i]]
2.若不选，则当前这个数不会影响到前i-1个数之和为j的方案总数，其f[i][j] = f[i-1][j]

综上：$f[i][j] = f[i-1][j] + f[i-1][j-v[i]]$

对于一维dp的优化，因为当前的状态是从上一层传递下来的，所以从大开始向小的作for循环遍历

求解代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int f[N],q[N];

int main()
{
    f[0] = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &q[i]);
    for(int i = 1; i <= n ; i++ )
        for(int j = m; j >= q[i]; j -- )
            f[j] += f[j - q[i]];
    cout<<f[m];
    return 0;
}