题目：278. 数字组合
题目描述
给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数，表示 A1,A2,…,AN。
输出格式
包含一个整数，表示可选方案数。
数据范围
1 ≤ N ≤ 100,
1 ≤ M ≤ 10000,
1 ≤ Ai≤ 100,
答案保证在 int 范围内。
时空限制
1s / 64MB
输入样例
4 4 1 1 2 2输出样例
3思路
初始化：
f[i][0]=1
代码1（二维数组）
#include<iostream>usingnamespacestd;constintMaxN=100+10,MaxV=10000+10;intN,V,f[MaxN][MaxV];intmain(){cin>>N>>V;f[0][0]=1;for(inti=1;i<=N;i++){intv;cin>>v;for(intj=0;j<=V;j++){f[i][j]=f[i-1][j];if(v<=j){f[i][j]+=f[i-1][j-v];}}}cout<<f[N][V];return0;}代码2（一维数组）
#include<iostream>usingnamespacestd;constintMaxV=10000+10;intN,V,f[MaxV];intmain(){cin>>N>>V;f[0]=1;for(inti=1;i<=N;i++){intv;cin>>v;for(intj=V;j>=v;j--){f[j]+=f[j-v];}}cout<<f[V];return0;}