算法提高课汇总

算法思路

理解题意

1. 限制
   • 货币面值恰好为$m$
   • 每个货币的数量没有限制
2. 目的
   • 数量, 货币面值恰好为$m$的方案数

即问题是完全背包求方案数, 与买书 思路一致.

代码实现

#include <iostream>

using namespace std;

typedef long long ll;

const int M = 3010;

int n, m;
ll dp[M];

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

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

    return 0;
}