Money Change Problem

#1

I have not understood the code so please explain the logic

#2

first, observe
1) Optimal Substructure
To count the total number of solutions, we can divide all set solutions into two sets.

  1. Solutions that do not contain mth coin (or Sm).
  2. Solutions that contain at least one Sm.
    Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).
    recursive sol:
    // Returns the count of ways we can

// sum S[0...m-1] coins to get sum n

int count( int S[], int m, int n )

{

// If n is 0 then there is 1 solution

// (do not include any coin)

if (n == 0)

return 1;

// If n is less than 0 then no

// solution exists

if (n < 0)

return 0;

// If there are no coins and n

// is greater than 0, then no

// solution exist

if (m <=0 && n >= 1)

return 0;

// count is sum of solutions (i)

// including S[m-1] (ii) excluding S[m-1]

return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

}
Dp; Solution:
int count( int S[], int m, int n )

{

int i, j, x, y;

// We need n+1 rows as the table

// is constructed in bottom up

// manner using the base case 0

// value case (n = 0)

int table[n + 1][m];

// Fill the enteries for 0

// value case (n = 0)

for (i = 0; i < m; i++)

table[0][i] = 1;

// Fill rest of the table entries

// in bottom up manner

for (i = 1; i < n + 1; i++)

{

for (j = 0; j < m; j++)

{

// Count of solutions including S[j]

x = (i-S[j] >= 0) ? table[i - S[j]][j] : 0;

// Count of solutions excluding S[j]

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

// total count

table[i][j] = x + y;

}

}

return table[n][m - 1];

}

so the idea is to judge whether it is better to include a particular coin of the array or not include it and then count both the ways and return the better answer

1 Like