注意事项：
本题为"dp动态规划—完全背包"的扩展题，和“背包模型—买书”的解法基本相同，dp思路和优化思路这里就不多讲。

题目：
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式
第一行，包含两个整数n和m。
接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
n≤15,m≤3000

输入:
3 10
1
2
5

输出：
10

#include 
#include 
#include 
#include 
using namespace std;typedef long long LL;
const int N = 3010;
int n, m;
int v[N];
LL f[N][N];         //需要开long long，否则爆int，具体原因是可以看作是组合数问题来求，C15 3000，遇到最坏情况long long也会爆掉int main() {cin >> n >> m;for (int i =1; i<=n; i++) cin >> v[i];f[0][0] = 1;    //选0个面值总和为0的方案也算一个方案//朴素版完全背包，这里可以优化为一维双循环，具体看完全背包那篇文章，有详解for (int i = 1; i<=n; i++) {for (int j = 0; j<=m; j++) {for (int k = 0; k*v[i]<=j; k++) {f[i][j] += f[i-1][j-k*v[i]];}}}cout << f[n][m];return 0;
}

思路：
这道题唯一需要注意的点就是数据范围，可以用组合数的方式来算出来最坏情况下应该是C(15, 3000)，long long都存不下，还好数据卡的不是那么死（

如果有所帮助请给个免费的赞吧~有人看才是支撑我写下去的动力！

声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流