题目描述

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

样例

输入样例：
3 10
1
2
5
输出样例：
10

算法

(DP,完全背包) $O(nm)$

可以转化为完全背包问题求方案数：

• 将组成货币的面值数$M$看作背包容量；
• 将每种货币的面值$v$ 看作体积为$v$的物品，每种物品都可以无限次使用；

时间复杂度

背包问题的时间复杂度为$O(nm)$。

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 3010;

int n, m;
LL f[N];

int main()
{
    cin >> n >> m;

    f[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int v;
        cin >> v;
        for(int j = v; j <= m; j++)
            f[j] += f[j-v];
    }
    cout << f[m] << endl;
    return 0;
}