07-25-2014, 01:52 AM
Making Change: Dynamic Programming Solution
The general coin change problem can be solved using Dynamic Programming. Set up a Table, C[1..k, 0..N] in which the rows denote available denominations, di; (1 _ i _ k) and columns denote the amount from 0 . . .N units, (0 _ j _ N). C[i, j] denotes the minimum number of coins, required to pay an amount j using only coins of denominations 1 to i. C[k, N] is the solution required.
To pay an amount j units, using coins of denominations 1 to i, we have two choices:
1. either chose NOT to use any coins of denomination i,
2. or chose at least one coin of denomination i, and also pay the amount (j - di).
To pay (j - di) units it takes C[i, j - di] coins. Thus,
C[i, j] = 1 + C[i, j - di]
Since we want to minimize the number of coins used,
C[i, j] = min(C[i - 1, j], 1 + C[i, j - di])
This is the forumulation!
The general coin change problem can be solved using Dynamic Programming. Set up a Table, C[1..k, 0..N] in which the rows denote available denominations, di; (1 _ i _ k) and columns denote the amount from 0 . . .N units, (0 _ j _ N). C[i, j] denotes the minimum number of coins, required to pay an amount j using only coins of denominations 1 to i. C[k, N] is the solution required.
To pay an amount j units, using coins of denominations 1 to i, we have two choices:
1. either chose NOT to use any coins of denomination i,
2. or chose at least one coin of denomination i, and also pay the amount (j - di).
To pay (j - di) units it takes C[i, j - di] coins. Thus,
C[i, j] = 1 + C[i, j - di]
Since we want to minimize the number of coins used,
C[i, j] = min(C[i - 1, j], 1 + C[i, j - di])
This is the forumulation!