【题解-Acwing】278. 数字组合

题目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二维数组#includeiostreamusingnamespacestd;constintMaxN10010,MaxV1000010;intN,V,f[MaxN][MaxV];intmain(){cinNV;f[0][0]1;for(inti1;iN;i){intv;cinv;for(intj0;jV;j){f[i][j]f[i-1][j];if(vj){f[i][j]f[i-1][j-v];}}}coutf[N][V];return0;}代码2一维数组#includeiostreamusingnamespacestd;constintMaxV1000010;intN,V,f[MaxV];intmain(){cinNV;f[0]1;for(inti1;iN;i){intv;cinv;for(intjV;jv;j--){f[j]f[j-v];}}coutf[V];return0;}结果