# 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.

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

```cpp
// 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();
}
```

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

```cpp
// 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);
}
```

```cpp
// 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);
}
```

{% hint style="info" %}
這題可以和[983. Minimum Cost For Tickets](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/~/drafts/-L_cjm5SOOqbLXm32kJx/primary/dynamic-programming/983.-minimum-cost-for-tickets)一起練習。
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/322.-coin-change.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.