Uva-674 – Coin Change

Short Problem Description:

Given the 5 coins 1,5,10,25,30 and an amount( assume, taka). You have to find the number of ways the amount can be made using these 5 coins.

Solution Approach:

This is an easy dp problem. So try to find overlapping sub-problem,
recurrence relation and also base case. This is a common technique to solve a dp problem.

In this problem I will try to find these…At first I declare a function f(i,j) which returns the number of ways of j taking first i coins.

Now,

f(i,j)=0, if i==0 base case
f(i,j)=1, if j<5 base case
f(i,j)=f(i-1,j) ,if(j-coin[i])=0 recurrence relation

Problem Link: Click Here

My Code: Click Here