dynamic programming - Coin change algorithm and pseudocode: Need clarification -

dynamic programming - Coin change algorithm and pseudocode: Need clarification -

i'm trying understand coin alter problem solution, having difficulty.

at the algorithmist, there pseudocode solution dynamic programming solution, shown below:

n = goal number s = [s1, s2, s3 ... sm] function sequence(n, m) //initialize base of operations cases = 0 n j = 0 m table[i][j] = table[i-s[j]][j] + table[i][j-1]

this pretty standard o(n^2) algorithm avoids recalculating same reply multiple times using 2-d array.

my issue two-fold:

how define base of operations cases , incorporate them in table[][] initial values how extract out different sequences table

regarding issue 1, there 3 base of operations cases algorithm:

if n==0, homecoming 1 if n < 0, homecoming 0 if n >= 1 && m <= 0, homecoming 0

how incorporate them table[][], not sure. finally, have no thought how extract out solution set array.

we can implement dynamic programming algorithm in @ to the lowest degree 2 different approaches. 1 top-down approach using memoization, other bottom-up iterative approach.

for beginner dynamic programming, recommend using top-down approach first since help them understand recurrence relationships in dynamic programming.

so in order solve coin changing problem, you've understood recurrence relationship says:

table[i][j] = table[i-s[j]][j] + table[i][j-1]

such recurrence relationship not well-defined since doesn't have boundary conditions. therefore, need define boundary conditions in order ensure recurrence relationship terminate without going infinite loop.

so happen when seek go downwards recursive tree?

if need calculate table[i][j], means number of approaches alter i using coins type 0 j, there several corner cases need handle:

1) if j == 0?

if j == 0 seek solve sub-problem table(i,j-1), not valid sub-problem. therefore, 1 boundary status is:

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

2) if i - s[j] < 0?

we need handle boundary case , know in such status should either not seek solve sub-problem or initialize table(i-s[j],j) = 0 of these cases.

so in all, if going implement dynamic programming top-down memoization approach, can this:

int f(int i, int j) { if(calc[i][j]) homecoming table[i][j]; calc[i][j] = true; if(j==0) { if(i==0) homecoming table[i][j]=1; else homecoming table[i][j]=0; } if(i>=s[j]) homecoming table[i][j]=table[i-s[j][j]+table[i][j-1]; else homecoming table[i][j]=table[i][j-1]; }

in practice, it's possible utilize value of table arrays help track whether sub-problem has been calculated before (e.g. can initialize value of -1 means sub-problem hasn't been calculated).

hope reply clear. :)

algorithm dynamic-programming coin-change