322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note: You may assume that you have an infinite number of each kind of coin.

Bottom-Up DP利用一個count array來從小的amount來逐漸掃描到大的amount，count[i]代表湊到i幣值的錢需要使用的最少硬幣數量。Pad一個dummy值在count array最前並初始化為0。

// Bottom-Up Dynamic Programming
int coinChange(vector<int>& coins, int amount) { // time: O(amount * # of coins); space: O(amount)
    vector<int> count(amount + 1, amount + 1);
    count[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (i >= coin)
                count[i] = min(count[i], count[i - coin] + 1);
        }
    }
    return count.back() > amount ? -1 : count.back();
}

Top-Down DP + memoization使用一個hashmap記錄錢的amount對應到最少的組成硬幣數量，以避免重複運算。

// Top-Down DP
int helper(vector<int>& coins, int amount, unordered_map<int, int>& memo) {
    if (amount < 0) return -1;
    if (memo.count(amount)) return memo[amount];
    int cur = amount + 1;
    for (int i = 0; i < coins.size(); ++i) {
        int tmp = helper(coins, amount - coins[i], memo);
        if (tmp >= 0)
            cur = min(cur, tmp + 1);
    }
    return memo[amount] = (cur == amount + 1 ? -1 : cur);
}
int coinChange(vector<int>& coins, int amount) { // time: O(amount * # of coins); space: O(amount)
    unordered_map<int, int> memo;
    memo[0] = 0;
    return helper(coins, amount, memo);
}

// Top-Down DP
int helper(vector<int>& coins, int target, vector<int>& memo) {
    if (target < 0) return -1;
    if (memo[target] != INT_MAX) return memo[target];
    for (int coin : coins) {
        int tmp = helper(coins, target - coin, memo);
        if (tmp >= 0) memo[target] = min(memo[target], tmp + 1);
    }
    return memo[target] = (memo[target] == INT_MAX ? -1 : memo[target]);
}
int coinChange(vector<int>& coins, int amount) { // time: O(amount * # of coins); space: O(amount)
    vector<int> memo(amount + 1, INT_MAX);
    memo[0] = 0;
    return helper(coins, amount, memo);
}

這題可以和983. Minimum Cost For Tickets一起練習。