Coin change with minimum coins

'''
Logic:
We will traverse the whole amount from 0.
and for every amount,we will traverse all the coins.
if current amount-current coin>=0 and check for amount form by
(current amount-current coin) in dp table,update the minimum of both.

dp[i] stores the minimum number of coins needed for amount i.
We initialize with infinity as an impossible high value (worse than any valid answer).
For each amount i, we check if we can reach it by adding a coin to a smaller amount i - coin.
If dp[amount] remains unchanged, it means there's no valid way to make up the amount.

'''

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[math.inf]*(amount+1)
        dp[0]=0
        for i in range(1,amount+1):
            for coin in coins:
                if i-coin>=0:
                    dp[i]=min(dp[i],dp[i-coin]+1)
        if dp[amount]==math.inf:
            return -1
        else:
            return dp[amount]