<p>You are given an integer array <code>coins</code> representing coins of different denominations and an integer <code>amount</code> representing a total amount of money.</p>

<p>Return <em>the fewest number of coins that you need to make up that amount</em>. If that amount of money cannot be made up by any combination of the coins, return <code>-1</code>.</p>

<p>You may assume that you have an infinite number of each kind of coin.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> coins = [1,2,5], amount = 11
<strong>Output:</strong> 3
<strong>Explanation:</strong> 11 = 5 + 5 + 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> coins = [2], amount = 3
<strong>Output:</strong> -1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> coins = [1], amount = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= coins.length &lt;= 12</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>0 &lt;= amount &lt;= 10<sup>4</sup></code></li>
</ul>

r'''
# Requirements

n = len(coins)
w = amount
1 <= n <= 12
0 <= w <= 10,000
1 <= coins[i] <= 2^31 - 1

# Edge cases

1. amount == 0
    - Return 0
2. Cannot make up amount using the provided coin values
    - Return -1

# Solutions

1. Brute force, backtracking
    - O(w^n) time, O(n) auxiliary space
2. Knapsack DP
    - O(n * w) time, O(n * w) auxiliary space
'''
INF = 10 ** 9

def coin_change_memo(coins: list[int], amount: int) -> int:
    memo = [[-1] * (amount + 1) for _ in range(len(coins))]

    def knapsack(i: int, target: int) -> int:
        if target == 0:
            return 0
        if i == len(coins):
            return INF
        if memo[i][target] > -1:
            return memo[i][target]

        memo[i][target] = knapsack(i + 1, target)
        if target >= coins[i]:
            memo[i][target] = min(memo[i][target], 1 + knapsack(i, target - coins[i]))

        return memo[i][target]

    ans = knapsack(0, amount)
    return ans if ans < INF else -1

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        return coin_change_memo(coins, amount)
38841