coin change ways

1def maxWays(coins,price):
2    n = len(coins)
3    # Define dp array
4    dp = [[None]*(price+1) for _ in range(n+1)]
5
6    # Initialise dp Array.
7    # If No of coins available is 0 then there is no way to pay. So dp[0][j] = 0
8    # If price = 0 then it is possible to pay considering null set. So dp[i][0] = 1
9
10    for i in range(n+1):
11        dp[i][0] = 1
12    for j in range(price+1):
13        dp[0][j] = 0
14
15    # A coin can be used only if its value is less than the price so coin[i] <= price
16    # Now if a coin is chosen once then it can be included any number of times
17
18    for  i in range(1,n+1):
19        for j in range(1,price+1):
20            # check if coin[i] < price
21            if coins[i-1] <= j:
22                dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
23            else:
24                dp[i][j] = dp[i-1][j]
25    return dp[n][price]
26
27
28if __name__ == '__main__':
29    coins = [1,2,3]
30    price = 5
31    ch = maxWays(coins,price)
32    print('Max Ways to Pay : ', ch)
33