Coin change with minimum coins

'''
Intuition:
- We want the minimum number of coins needed to make every value from 0 to amount.
- Let dp[x] = minimum coins required to make sum x.
- Base case: dp[0] = 0 (0 amount needs 0 coins).
- For every target sum i (1 to amount):
    - Try using each coin.
    - If we take coin, then the remaining sum is (i - coin).
    - So candidate answer becomes: dp[i - coin] + 1
    - Take the minimum over all coins.

- If dp[amount] stays infinity, it means no combination can form the amount.

Time Complexity: O(amount * len(coins))
Space Complexity: O(amount)
'''
import math
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[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]==inf:
            return -1
        else:
            return dp[amount]


#M-2
import math
def fun(n,rem,coins,dp):
    if rem==0:
        return 0
    if n<0 or rem<0:
        return math.inf

    if dp[n][rem]!=-1:
        return dp[n][rem]
    take=math.inf
    if rem>=coins[n]:
        take=1+fun(n,rem-coins[n],coins,dp)
    not_take=fun(n-1,rem,coins,dp)
    dp[n][rem]=min(take,not_take)
    return dp[n][rem]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[[-1]*(amount+1) for _ in range(len(coins))]
        n=len(coins)
        ans=fun(n-1,amount,coins,dp)
        return ans if ans!=math.inf else -1