USACO 2.3 Money System

Very classic DP problem.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
int COINS;
vector<long long> dp(100001, 0);
vector<long> coins;
void compute() {
    dp[0] = 1;
    for (int i = 0; i < COINS; ++i) {
        for (int j = coins[i]; j <= N; ++j) {
            dp[j] += dp[j - coins[i]];
        }
    }
}

int main() {
    ifstream fin("money.in");
    ofstream fout("money.out");
    fin >> COINS >> N;
    for (int i = 0; i < COINS; ++i) {
        int c; fin >> c; coins.emplace_back(c);
    }
    compute();
    fout << dp[N] << endl;
}