题解 | #换钱的最少货币数#

01背包

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    int minMoney(vector<int>& arr, int aim) {
        int n = arr.size();
        int dp[aim + 1];
        memset(dp, inf, sizeof(dp));
        dp[0] = 0;
        for(int i = 0; i < n; i ++){
            for(int v = arr[i]; v <= aim; v ++){
                dp[v] = min(dp[v], dp[v - arr[i]] + 1);
            }
        }
        return dp[aim] == inf ? -1 : dp[aim];
    }
};

记录具体选择

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    int minMoney(vector<int>& arr, int aim) {
        int n = arr.size();
        int dp[n + 1][aim + 1];
        int choose[n + 1][aim + 1];
        memset(dp, inf, sizeof(dp));
        memset(choose, -1, sizeof(choose));
        dp[0][0] = 0;
        for(int i = 1; i <= n; i ++){
            for(int v = 0; v <= aim; v ++){
                if(v < arr[i - 1]) dp[i][v] = dp[i - 1][v];
                else{
                    if(dp[i - 1][v] > dp[i][v - arr[i - 1]] + 1){
                        dp[i][v] = dp[i][v - arr[i - 1]] + 1;
                        choose[i][v] = i;
                    }else dp[i][v] = dp[i - 1][v];
                }
            }
        }
        if(dp[n][aim] == inf) return -1;
        int i = n, v = aim;
        vector<int> res;
        while(i > 0){
            cout << i << ":" << v << ":" << choose[i][v] << " ";
            if(choose[i][v] != -1){
                i = choose[i][v];
                v -= arr[i - 1];
                res.push_back(arr[i - 1]);
            }else i --;

        }
        cout << endl;
        for(int i = 0; i < res.size(); i ++) cout << res[i] << " ";
        return dp[n][aim] == inf ? -1 : dp[n][aim];
    }
};