Leetcode 322. Coin Change

Problem

Dynamic Programming, Medium

Example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Input: coins = [2], amount = 3
Output: -1

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

Approach

Using dynamic programming, we can solve for the counts by storing all the coin values in dp array

Here is the Python code for the solution:

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

        for a in range(amount):
            for c in coins:
                if a-c >= 0:
                    dp[a] = min(dp[a], 1+dp[a-c])

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

Time Complexity and Space Complexity

Time Complexity: $O(n * t)$ where $n$ is length of coins $t$ is amount

Space Complexity: $O(t)$