You are given an array of integers nums representing coin denominations and an integer amount representing a total amount of money. You need to 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:

nums = [1, 2, 5]
amount = 11

Answer: 3 (11 = 5 + 5 + 1)

Example 2:

nums = [2]
amount = 3

Answer: -1 (You cannot make up the amount 3 with only coins of denomination 2)

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 1000
0 <= amount <= 10000

Clarifications:

Are the coin denominations always positive integers?
Is there a limit to the number of times each coin can be used?
If the amount is 0, what should the function return?

Coin Change

Problem Description

Example 1:

nums = [1, 2, 5]
amount = 11

Answer: 3 (11 = 5 + 5 + 1)

Example 2:

nums = [2]
amount = 3

Answer: -1 (You cannot make up the amount 3 with only coins of denomination 2)

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 1000
0 <= amount <= 10000

Clarifications:

Are the coin denominations always positive integers? Yes
Is there a limit to the number of times each coin can be used? No
If the amount is 0, what should the function return? 0

Brute Force Solution

A brute force solution would involve recursively trying all possible combinations of coins to reach the target amount. This would be very inefficient.

def coin_change_brute_force(coins, amount):
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    min_coins = float('inf')
    for coin in coins:
        result = coin_change_brute_force(coins, amount - coin)
        if result != -1:
            min_coins = min(min_coins, result + 1)

    return min_coins if min_coins != float('inf') else -1

Optimal Solution (Dynamic Programming)

We can use dynamic programming to solve this problem efficiently. We create a DP table dp where dp[i] represents the minimum number of coins needed to make up the amount i. We initialize dp[0] to 0, as it takes 0 coins to make up an amount of 0. All other entries are initialized to infinity.

Then, for each coin denomination, we iterate through the dp table and update the values. Specifically, if dp[i - coin] is not infinity, it means that we can make up the amount i - coin. Thus, we can make up the amount i by adding the current coin, and the number of coins needed would be dp[i - coin] + 1. We take the minimum of the current value of dp[i] and dp[i - coin] + 1.

Finally, we return dp[amount] if it's not infinity, otherwise we return -1.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Example

Let's trace the optimal solution for coins = [1, 2, 5] and amount = 11.

Initialize dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
For coin = 1:
- dp[1] = min(inf, dp[0] + 1) = 1
- dp[2] = min(inf, dp[1] + 1) = 2
- ... dp[11] = min(inf, dp[10] + 1) = 11
For coin = 2:
- dp[2] = min(2, dp[0] + 1) = 1
- dp[3] = min(inf, dp[1] + 1) = 2
- dp[4] = min(inf, dp[2] + 1) = 2
- ...dp[11] = min(11, dp[9] + 1) = 6
For coin = 5:
- dp[5] = min(inf, dp[0] + 1) = 1
- ...dp[10] = min(6, dp[5] + 1) = 2
- dp[11] = min(6, dp[6] + 1) = 3

Finally, dp[11] = 3, so the answer is 3.

Big(O) Time Complexity Analysis

The time complexity of the dynamic programming solution is O(n*amount), where n is the number of coin denominations and amount is the target amount. This is because we have a nested loop: the outer loop iterates through each coin denomination (n iterations), and the inner loop iterates through all amounts from coin to the target amount (amount iterations).

Big(O) Space Complexity Analysis

The space complexity of the dynamic programming solution is O(amount), as we use a DP table of size amount + 1 to store the minimum number of coins needed for each amount from 0 to amount.

Edge Cases

Amount is 0: The function should return 0, as no coins are needed.
No solution possible: If the amount cannot be made up by any combination of the coins, the function should return -1. This is handled by checking if dp[amount] is still infinity after the dynamic programming process.
Empty coin array: If the coin array is empty and the amount is not 0, then no solution is possible, and we should return -1. If amount is 0, then we return 0.
Large amount: If the amount is very large, the space complexity could be a concern. However, the constraint specifies that amount <= 10000, so it's not a major issue.
Coin values are zero: If the coin array has values equal to zero, it will lead to an infinite loop. But according to the constraints, 1 <= nums[i] <= 1000, so the coin values can't be zero.

def coin_change_handling_edge_cases(coins, amount):
    if amount == 0:
        return 0
    
    if not coins:
      return -1

    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Given coin denominations and a total amount, find the fewest number of coins to make up that amount.