Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <functional>
- #include <iostream>
- #include <vector>
- using namespace std;
- #define MAX_VALUE 100000
- vector<int> DP(MAX_VALUE + 1, MAX_VALUE + 1);
- template <typename Less, typename... T>
- constexpr auto& m_min(Less&& less, const T&... values) {
- return std::min({ std::cref(values)..., }, std::forward<Less>(less)).get();
- }
- int safe_access(vector<int> DP, int index) {
- if (index < 0) {
- return MAX_VALUE + 1;
- }
- return DP.at(index);
- }
- void coin_change(int value) {
- DP[0] = 1;
- DP[1] = DP[5] = DP[10] = DP[20] = DP[100] = 1;
- for (int i = 1; i <= value; i++) {
- DP[i] = m_min(
- std::less<int>(),
- safe_access(DP, i),
- safe_access(DP, i - 1) + 1,
- safe_access(DP, i - 5) + 1,
- safe_access(DP, i - 10) + 1,
- safe_access(DP, i - 20) + 1,
- safe_access(DP, i - 100) + 1
- );
- }
- }
- int coin_change_rec(int value) {
- if (value < 0) return MAX_VALUE + 1;
- if (value == 0) return 0;
- if (value == 1 || value == 5 || value == 10 || value == 20 || value == 100) {
- return 1;
- }
- return 1 + m_min(
- std::less<int>(),
- coin_change_rec(value - 1),
- coin_change_rec(value - 5),
- coin_change_rec(value - 10),
- coin_change_rec(value - 20),
- coin_change_rec(value - 100)
- );
- }
- int main() {
- int value;
- cin >> value;
- coin_change(value);
- cout << DP.at(value);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement