Introduction

In this blog post, we will explore how to solve the LeetCode problem "322" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 Constraints: 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104

Explanation

• Dynamic Programming: We use dynamic programming to build up a table dp where dp[i] stores the minimum number of coins needed to make up amount i.

• Bottom-up Approach: We initialize dp[0] to 0 (no coins needed for amount 0) and all other dp[i] to infinity. We then iterate through each amount from 1 to amount, and for each amount, we iterate through the coins. If a coin's value is less than or equal to the current amount, we update dp[i] with the minimum of its current value and dp[i - coin] + 1.

• Result: After the loop, dp[amount] will contain the minimum number of coins needed to make up the target amount. If dp[amount] is still infinity, it means the amount cannot be made up by the given coins, so we return -1.

• Runtime Complexity: O(amount * number of coins). Storage Complexity: O(amount).

Code

    def coin_change(coins: list[int], amount: int) -> int:
    """
    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

    Constraints:
    1 <= coins.length <= 12
    1 <= coins[i] <= 231 - 1
    0 <= amount <= 104
    """
    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'):
        return -1
    else:
        return dp[amount]