Coin Change II

'''
Unbounded 0/1 Knapsack
Same like Coin Change I but here if cur_remaining==0, means you got one combination so return 1
if i<0, means no coins left to select so return 0
dp[i][j]=sum of take+not_take because dp[i][j] denotes the maxium coins composition that is possible by 0->ith coins and target as j
'''

def fun(arr,i,cur_remaining, dp):
    if cur_remaining==0:
        return 1
    if i<0:
        return 0
    if dp[i][cur_remaining]!=-1:
        return dp[i][cur_remaining]
    coin=arr[i]
    take=0
    if cur_remaining>=coin:
        take=fun(arr,i,cur_remaining-coin, dp)
    not_take=fun(arr,i-1,cur_remaining,dp)
    dp[i][cur_remaining]=take+not_take
    return dp[i][cur_remaining]


class Solution:
    def change(self, amount:int, coins: List[int]) -> int:
        dp=[[-1]*(amount+1) for _ in range(len(coins))]
        return fun(coins,len(coins)-1,amount,dp)