Let coin[] be the array of coins and N is the given number that you have to repr
ID: 3857103 • Letter: L
Question
Let coin[] be the array of coins and N is the given number that you have to represent using the list of coins and you may assume that you have infinite supply of coins of one type.
The number of ways to represent the number N with the given denomiation of coins is:
T(n) = T(n)(coin,i1,N)+T(n)(coin,i,Ncoin[i]);
Taken from source: https://www.quora.com/What-is-an-easy-way-to-understand-the-coin-change-problem-in-dynamic-programming/answer/Ajay-Kumar-1779
Prove that the given recurrence is increasing without using closed form for the values coin = [4, 6, 10], i = 2 and N any arbitrary even natural number greater than 4
Explanation / Answer
Given Formula:
T(n) = T(n)(coin,i1,N)+T(n)(coin,i,Ncoin[i]);
recurrenc problem solved as per as the given reffernce link:
Here i=2 and arbitary even natural number is :60
so formation of 60 by using [4,6, 10] there are 8 ways i.e:{4*15},{6*10},{5*10,4,6}.......so on
So the minimum recurrence closed to the given values of coin:[4,6,10] is : 8
This the algorithm for find the above problem:
int count( int coin[], int m, int n )
{
if (n == 0)
return 1;
if (n < 0)
return 0;
if (m <=0 && n >= 1)
return 0;
return count( coin, m - 1, n ) + count( S, m, n-coin[m-1] );
int count( int coin[], int m, int n )
{
if (n == 0)
return 1;
if (n < 0)
return 0;
if (m <=0 && n >= 1)
return 0;
return count( coin, m - 1, n ) + count( S, m, n-coin[m-1] );
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.