dp-coin-change.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll change(int t, vector<int> &v, vector<int> &dp) {
	if (t == 0) return 0;
	ll m = INT_MAX;

	if (dp[t] != -1) return dp[t];

	for (auto coin : v) {
		if (t - coin >= 0) m = min(m, change(t - coin, v, dp) + 1);
	}

	return dp[t] = m;
}

int main() {
	int n, t; cin >> n >> t;
	vector<int> v(n);
	vector<int> dp(t + 1, -1);
	for (auto &d : v) cin >> d;

	cout << change(t, v, dp) << endl;

	return 0;
}

greedy-coin-change.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, t; cin >> n >> t;
	vector<int> v;
	while (n--) {
		int x; cin >> x;
		v.push_back(x);
	}

	int c = 0;

	sort(v.begin(), v.end(), greater<int>());

	for (auto d : v) {
		int coins = (t / d);
		c += coins;
		t %= d;
	}

	cout << c << endl;

	return 0;
}