Coin Change

[The_Madman]

Can anyone convert the Pseudo code into c/c++ (?) :

**********************************************************
func count( n, m )
initialize table with base cases

for i from 0 to n
for j from 0 to m
table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]

return table[ n, m ]
*********************************************************

for better understanding please have a look on this site :
http://www.algorithmist.com/index.php/Coin_Change

The main problem i'm facing is how to initialize the table with base
cases ? It seems to require negative array indexing, but c/c++ doesn't
allow it. So there must be other way...

Regards

[tryit1]

From the same link , these are the base cases. So fill the table for all i=0 as 1 and others as 0 .
The ? operator is used instead of if

if(a==0)
m
else n
is written as (a==0)?m:n or it can be written as a?n:m

Code: Select all

func count( n, m )
  initialize table with base cases


  for i from 0 to n 
    for j from 0 to m ( Do j from 1 to m since all j<1 is 0 except i=j=0 when it is 1)
      table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]

Table[i -S_j ,j] is >=1 only if i>=S_j, so other values are 0 from below. 
 
table[i,j]= ((i>=S_j) ? table[i-S_j,j] : 0)  +  ((i==0) ?1:((j==0)?0:table[i,j-1]) )




func count( n, m )
  if ( n == 0 ) 
    return 1
  if ( n < 0 )
    return 0
  if ( m <= 0 and n >= 1 )
    return 0

  return count( n, m - 1 ) + count( n - S_m, m )

[The_Madman]

Thanks that helped a lot! But I've a few questions. I followed the algo as below:

Code: Select all

for(i=0; i<n; i++)
		for(j=0; j<m; j++)
		{	
			if(i==0) table[i][j] = 1;
			else if(i-s[j]<0) table[i][j] = 0;
			else if(i>=1 && j==0) table[i][j] = 0;
			else table[i][j] = table[i][j-1] + table[i-s[j]][j];			
		}

why didn't it work?
And, you wrote:

Code: Select all

table[i][j]= ((i>=s[j]) ? table[i-s[j]][j] : 0)  +  ((i==0) ?1:((j==0)?0:table[i][j-1]));

where,

Code: Select all

((i==0) ?1:((j==0)?0:table[i][j-1]));

seems violating the algo. here j stands for m right? If so when j=0 it means S_j to some element. Say the largest or the the smallest. But, the algo says:

Code: Select all

return 0 while n>=1 && m<=0

where this m means there is no coin left.
Hope you'll clear it.

Thanks again.

[tryit1]

Initialize the table to 0.
and
Remove these lines

Code: Select all

         else if(i-s[j]<0) table[i][j] = 0;
         else if(i>=1 && j==0) table[i][j] = 0;

Where did it not work ? Can you give inputs /output where it failed ?

Code: Select all

((i==0) ?1:((j==0)?0:table[i][j-1])); means

if(i==0)
     ans is 1
else 
{
      if(j==0) 
                ans is 0
     else
        table[i][j];
}

Intrepret it as when you have to make value 0, ways is 1
When you have to make a value >0 , with 0 coins , number of ways is 0
otherwise it is table[j-1].

So the number of ways to wake i $ with j coins is

i$ with j-1 coins (not selecting jth coin)
and i-s[j]$ with j coins ( selecting the jth coin)

[The_Madman]

Thanks for your reply. Can you please give any reason why should I remove those lines? Since it simply replaces the bases cases. And are similar to your code.
Say,

Code: Select all

else if(i-s[j]<0) table[i][j] = 0;

is similar to

Code: Select all

((i>=s[j]) ? table[i-s[j]][j] : 0)
or, if (i>=s[j] not true then 0)

And,

Code: Select all

else if(i>=1 && j==0) table[i][j] = 0;

is similar to

Code: Select all

((i==0) ?1:[b]((j==0)?0[/b]:table[i][j-1]))
or if(i==0) is false and (j==0) is true then 0

My code didn't work for the input 50. The output will be 50 too. But, it returns 49!
Regards