Coin change ways
def maxWays(coins,price):
n = len(coins)
# Define dp array
dp = [[None]*(price+1) for _ in range(n+1)]
# Initialise dp Array.
# If No of coins available is 0 then there is no way to pay. So dp[0][j] = 0
# If price = 0 then it is possible to pay considering null set. So dp[i][0] = 1
for i in range(n+1):
dp[i][0] = 1
for j in range(price+1):
dp[0][j] = 0
# A coin can be used only if its value is less than the price so coin[i] <= price
# Now if a coin is chosen once then it can be included any number of times
for i in range(1,n+1):
for j in range(1,price+1):
# check if coin[i] < price
if coins[i-1] <= j:
dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[n][price]
if __name__ == '__main__':
coins = [1,2,3]
price = 5
ch = maxWays(coins,price)
print('Max Ways to Pay : ', ch)