# Solving Leetcode Interviews in Seconds with AI: Coin Change


	# 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](https://www.chatmagic.app), 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
	```python
	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]
	```