找零

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？

输入描述: 一行，包含一个数N。

输出描述: 一行，包含一个数，表示最少收到的硬币数。

输入例子1: 200

输出例子1: 17

例子说明1: 花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。

Solutions

1. greedy approach

#include <bits/stdc++.h>

using namespace std;

int main() {
    int remain; cin >> remain;
    remain = 1024 - remain;
    int num = 0;
    for (auto d : {64, 16, 4, 1}) {
        num += remain / d; remain %= d;
    }
    cout << num << endl;
}

1. dynamic programming

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n; cin >> n;
    n = 1024 - n;
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0 ;
    for (int i = 1; i <= n; i++) {
        for (auto d : {1, 4, 16, 64}) {
            if (i - d >= 0)
                dp[i] = min(dp[i], dp[i - d] + 1);
        }
    }
    cout << dp[n] << endl;
}