1021.货币系统

算法：

完全背包问题

• 状态表示：$\color{red}{f[i][j]}$表示前i种货币中组成面值为j的集合

• 状态计算：$f[i][j]=f[i-1][j]+f[i][j-x]$

代码：

#include<iostream>
using namespace std;

const int N = 3010;
int n,m;
long long f[N];

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

时间复杂度：$o(mn)$