# [Coin Change](https://leetcode.com/problems/coin-change/)
###### tags: `Leetcode`, `Medium`, `Dynamic Programming`

## Approach

* Initialize a `dp` array to hold `amount + 1` blocks with value as `amount + 1` as that would me the maximum value
* `dp[0] = 0` becuase we do not need any coins to make $0
* Iterate through every coin denomination for every index position of the `dp` array. If `(index - coin_value)` is positive then, `dp[index] = min(dp[index], 1 + dp[index - coin_value])`
* Finally return `dp[amount]` if it is not equal to `amount + 1` otherwise return `-1`

## Asymptotic Analysis
### Time Complexity: **O(M*N)**
### Space Complexity: **O(M)**
M = Amount
N = Length of coins

## Code

from typing import List


class CoinChange:
    def coin_change(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for index in range(1, len(dp)):
            for coin in coins:
                if index - coin >= 0:
                    dp[index] = min(dp[index], 1 + dp[index - coin])
        return dp[amount] if dp[amount] != amount + 1 else -1


input_coins, input_amount = [1, 2, 5], 11
cc = CoinChange()
print(f"Minimum number of coins for the given input amount = {cc.coin_change(input_coins, input_amount)}")