100Days of Code #Day22

We are going back to solving a programming question today. As we have seen before Dynamic programming involves splitting a problem into series of sub problems solving them and storing the result to avoid re computations.

Okay let’s jump on to the question,

Given an array of distinct positive integers representing coin denominations and a single non-negative integer n representing a target amount of money, write a function that returns the number of ways to make change for that target amount using the given coin denominations.

Sample Input

n=6

denoms = [1,5]

Sample Output:

2

Now, can we solve this in a normal looping method, we can but it will be taking too much of time and too much of looping. We have to find several set of combinations and check whether that will add up to 6.

Now, the dynamic programming approach, Okay where i have to split into small problems. Since we have to reach target by the denominations we have to split the target. Can we write the target as combination of denominations

6 = 5 + 1

6 = 1+ 1+1+1+1+1 (this too can be aggregated to 5+1)

Okay then Number of ways to reach 5

5 = 1+1+1+1+1 (this can be aggregated to 4+1_

5 = 5

Going on until 1 we can split the sub problem as follows for each denomination coin F(c) we can deduce the following condition

for each F(c)

if(F(i-c)>0)

F(i) = F(i)+F(i-c)

Another Example:

For each coin denomination we are checking number of ways to reach the number to which when coin added reaches target is greater than 0. If so add those possibilities to the current index’s possibilities.

#100DaysOfCode #Day22