信息学奥赛一本通T1273-货币系统(动态规划)

解题思路: 动态规划

注意事项: 如果用金额作为外循环，则会有重复，比如总金额3时的可能性1,2和2,1。这两种情况只能算作一种。因此需要将每种货币作为外循环，并且内循环从小到大，比如货币为1时，可以依次获得dp[1], dp[2], ... dp[m]为1。

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 10000;

int a[N];

int dp[N];

int main()

{

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {

        cin >> a[i];

    }

    dp[0] = 1;

    for (int i = 0; i < n; i++) {

        for (int j = a[i]; j <= m; j++) {

            dp[j] += dp[j - a[i]];     

        }

    }

    cout << dp[m] << endl;

    return 0;

}