Introduction

The task is to find the number of ways we can make the change of given N cents having infinite supply of Coins = { C₁, C₂,C₃ …. C_n}  valued coins.

Program

Approach 1

def sol(array, length, Ncents):


    result_table = [[0 for count in range(length)] for count in range(Ncents+1)]


    for x in range(length):
        result_table[0][x] = 1


# Fill table in bottom up manner
    for x in range(1, Ncents+1):
        for y in range(length):
#Do not contain lth coin
            count = result_table[x - array[y]][y] if x-array[y] >= 0 else 0
#Contain lth coin
            count1 = result_table[x][y-1] if y >= 1 else 0


            result_table[x][y] = count + count1


    return result_table[Ncents][length-1]


ip_array = [1, 2, 5, 10]
Ncents = int(input("Enter the value: "))
print("The number of solutions are: ",sol(ip_array, len(ip_array) , Ncents))

Output:

Approach 2

def sol(arr,length, N):


    result_table = [0 for k in range(N+1)]


    result_table[0] = 1
# Update table if index >= value of picked coin
    for x in range(0,length):
        for y in range(arr[x],N+1):
            result_table[y] += result_table[y-arr[x]]


    return result_table[N]


ip_array = [1, 2, 5, 10]
Ncents = int(input("Enter the value: "))
print("The number of solutions are: ",sol(ip_array, len(ip_array) , Ncents))

Output

Explanation

There can be two sub-problems to the given problem:

• Solution containing nth coin
• Solution do not contacting nth coin.

The total count can be obtained by adding both the solutions.