货币系统

本题属于背包问题中的方案数求解问题 + 完全背包模板

1.方案数求解

（1）通过闫氏DP分析背包问题，可以得出$f[i,j]$的实际含义为：从前i个物体中挑选若干个出来，其总价值为j的方案个数

（2）$f[i,j]$是属于求$count$类型的题目
（3）递推式推导：

• 如果不从第i个货币中挑选，那么其可能的方案数为$f[i-1][j]$
• 如果从第i个货币中挑选，那么其可能的方案数为$f[i-1][j-v[i]]$

综上所属，可知递推表达式如下：
$f[i][j] = f[i-1][j] + f[i-1][j-v[i]]$

2.完全背包

完全背包的三维式可以优化成二维，二维又可以优化成一维，但是要注意的是：第二层嵌套循环是从小到大循环的,进而有了如下的递推关系：

for(int i = 1; i <= n; i ++ )
{
    for(int j = v[i]; j <= m; j ++ )
        d[j] = d[j] + d[j - v[i]];
}

3.方案数求解的注意事项

一般方案数的求解都会是个很大的值，建议直接开long long，本题如果不开long long，会被卡3组数据

解题代码：

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

using namespace std;

const int N = 3020;

int n, m;
int v[N];
long long d[N];

int main()
{
    d[0] = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &v[i]);

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = v[i]; j <= m; j ++ )
            d[j] = d[j] + d[j - v[i]];
    }

    printf("%lld", d[m]);

    return 0;

}