[LeetCode] 322. Coin Change

1. Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

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

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

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

2. Thoughts

Use DP.
Use the fact that dp[x] is equal to dp[x-a]+1
assuming a is one of the coins

3. Tips learned

4. My solution

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

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

        if dp[amount] == float("inf"):
            dp[amount] = -1

        return dp[amount]

189/189 cases passed (778 ms)
Your runtime beats 66.46 % of python3 submissions
Your memory usage beats 61.12 % of python3 submissions (17 MB)

5. AI Solution and Improvements

Your solution is already a very efficient way to solve the problem you've described. It uses dynamic programming to build up a solution to the amount by iteratively calculating the minimum number of coins required to make each smaller amount. This way, it ensures that by the time you calculate the number of coins needed for the final amount, you have considered all possible combinations of coins.

However, a few minor improvements and clarifications can be made to enhance your code or the understanding of it:

1. Clarify the Algorithm with Comments: Adding comments can help others (and future you) understand the logic behind your algorithm more quickly.

2. Early Stopping: In cases where the coins array is sorted, or if you sort it and the largest coin is smaller than the amount, you can potentially stop early. However, given that you have an infinite supply of each coin and are looking for any possible combination, this optimization may not significantly impact the overall performance.

3. Code Optimization: Your code is already optimized for the problem statement. The use of dynamic programming here is apt because it avoids recalculating solutions to subproblems, a hallmark of inefficient recursive approaches.

4. Alternative Approaches: While your dynamic programming approach is already one of the most efficient for this problem, exploring other methods like greedy algorithms (which work in specific scenarios where the coin denominations are multiples of each other) could be intellectually stimulating but not necessarily more efficient in this case.

Let's refine your solution with some comments for clarity:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Initialize DP array where dp[i] is the fewest number of coins needed for amount i
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0  # Base case: 0 coins are needed for amount 0

        # Build up the dp array from 1 to amount
        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    # If the coin is smaller than the current amount,
                    # update the dp[i] to the minimum of its current value
                    # or the value of dp[i - coin] + 1
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        # If dp[amount] is still infinity, it means the amount cannot be made up by any combination of the coins
        return dp[amount] if dp[amount] != float("inf") else -1

This code essentially does the same thing as your original solution but includes comments for better understanding. Your original algorithm is efficient and well-suited to the problem, leveraging dynamic programming's strength in solving problems involving making decisions that depend on subproblems. There isn't a fundamentally better algorithm for this problem since dynamic programming is the most suitable approach for the coin change problem due to its nature of overlapping subproblems and the need for an optimal solution.