Coin Change

'''
Unbounded Knapsack: here find the target by choosing the coins of the array but you can choose multiple times the same coin.
In the dp table here, rows denotes all the indices of the coins, and column denotes the target remaining so dp[i][j] says minimum
number of coins possible to get the jth target but by using 0->ith coins.

Base Cases:
1.if target_remaining==0, means you achieved your target, so just return 0.
2.if i<0, means you didn't achieve the target even after exhausing all the coins combinations so we have to ignore this case completely
so to do that return inf because we are comparing the minimum of take and not_take so this case will automatically eliminated.
3.initialise take with inf because if take case is not there, then you should completely ignore this case.
'''
import math
def fun(arr,i,cur_remaining, dp):
    if cur_remaining==0:
        return 0
    if i<0:
        return math.inf
    if dp[i][cur_remaining]!=-1:
        return dp[i][cur_remaining]
    coin=arr[i]
    take=math.inf
    if cur_remaining>=coin:
        take=1+fun(arr,i,cur_remaining-coin, dp)
    not_take=fun(arr,i-1,cur_remaining,dp)
    dp[i][cur_remaining]=min(take,not_take)
    return dp[i][cur_remaining]


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