a good print of what happens inside program UVA 147 dollars (dp)
In this program I only have 3 type of coins - 5c , 10c, 20c ; max amount 30 cents!
http://codepad.org/BypQJeDa
=================================================================
EFORE THE FILLING TABLE , all ways to change(cells) are
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0
using coins 5,
cur amount(j): temp: (j- temp): ways[j]: ways[j- temp]: ways[j] + ways[j- temp]:
5 5 0 ways[5] = 0 ways[0] = 1 ways[5] + ways[0]= 1
6 5 1 ways[6] = 0 ways[1] = 0 ways[6] + ways[1]= 0
7 5 2 ways[7] = 0 ways[2] = 0 ways[7] + ways[2]= 0
8 5 3 ways[8] = 0 ways[3] = 0 ways[8] + ways[3]= 0
9 5 4 ways[9] = 0 ways[4] = 0 ways[9] + ways[4]= 0
10 5 5 ways[10] = 0 ways[5] = 1 ways[10] + ways[5]= 1
11 5 6 ways[11] = 0 ways[6] = 0 ways[11] + ways[6]= 0
12 5 7 ways[12] = 0 ways[7] = 0 ways[12] + ways[7]= 0
13 5 8 ways[13] = 0 ways[8] = 0 ways[13] + ways[8]= 0
14 5 9 ways[14] = 0 ways[9] = 0 ways[14] + ways[9]= 0
15 5 10 ways[15] = 0 ways[10] = 1 ways[15] + ways[10]= 1
16 5 11 ways[16] = 0 ways[11] = 0 ways[16] + ways[11]= 0
17 5 12 ways[17] = 0 ways[12] = 0 ways[17] + ways[12]= 0
18 5 13 ways[18] = 0 ways[13] = 0 ways[18] + ways[13]= 0
19 5 14 ways[19] = 0 ways[14] = 0 ways[19] + ways[14]= 0
20 5 15 ways[20] = 0 ways[15] = 1 ways[20] + ways[15]= 1
21 5 16 ways[21] = 0 ways[16] = 0 ways[21] + ways[16]= 0
22 5 17 ways[22] = 0 ways[17] = 0 ways[22] + ways[17]= 0
23 5 18 ways[23] = 0 ways[18] = 0 ways[23] + ways[18]= 0
24 5 19 ways[24] = 0 ways[19] = 0 ways[24] + ways[19]= 0
25 5 20 ways[25] = 0 ways[20] = 1 ways[25] + ways[20]= 1
26 5 21 ways[26] = 0 ways[21] = 0 ways[26] + ways[21]= 0
27 5 22 ways[27] = 0 ways[22] = 0 ways[27] + ways[22]= 0
28 5 23 ways[28] = 0 ways[23] = 0 ways[28] + ways[23]= 0
29 5 24 ways[29] = 0 ways[24] = 0 ways[29] + ways[24]= 0
30 5 25 ways[30] = 0 ways[25] = 1 ways[30] + ways[25]= 1
*****************************************************
using coins 5, 10,
cur amount(j): temp: (j- temp): ways[j]: ways[j- temp]: ways[j] + ways[j- temp]:
10 10 0 ways[10] = 1 ways[0] = 1 ways[10] + ways[0]= 2
11 10 1 ways[11] = 0 ways[1] = 0 ways[11] + ways[1]= 0
12 10 2 ways[12] = 0 ways[2] = 0 ways[12] + ways[2]= 0
13 10 3 ways[13] = 0 ways[3] = 0 ways[13] + ways[3]= 0
14 10 4 ways[14] = 0 ways[4] = 0 ways[14] + ways[4]= 0
15 10 5 ways[15] = 1 ways[5] = 1 ways[15] + ways[5]= 2
16 10 6 ways[16] = 0 ways[6] = 0 ways[16] + ways[6]= 0
17 10 7 ways[17] = 0 ways[7] = 0 ways[17] + ways[7]= 0
18 10 8 ways[18] = 0 ways[8] = 0 ways[18] + ways[8]= 0
19 10 9 ways[19] = 0 ways[9] = 0 ways[19] + ways[9]= 0
20 10 10 ways[20] = 1 ways[10] = 2 ways[20] + ways[10]= 3
21 10 11 ways[21] = 0 ways[11] = 0 ways[21] + ways[11]= 0
22 10 12 ways[22] = 0 ways[12] = 0 ways[22] + ways[12]= 0
23 10 13 ways[23] = 0 ways[13] = 0 ways[23] + ways[13]= 0
24 10 14 ways[24] = 0 ways[14] = 0 ways[24] + ways[14]= 0
25 10 15 ways[25] = 1 ways[15] = 2 ways[25] + ways[15]= 3
26 10 16 ways[26] = 0 ways[16] = 0 ways[26] + ways[16]= 0
27 10 17 ways[27] = 0 ways[17] = 0 ways[27] + ways[17]= 0
28 10 18 ways[28] = 0 ways[18] = 0 ways[28] + ways[18]= 0
29 10 19 ways[29] = 0 ways[19] = 0 ways[29] + ways[19]= 0
30 10 20 ways[30] = 1 ways[20] = 3 ways[30] + ways[20]= 4
*****************************************************
using coins 5, 10, 20,
cur amount(j): temp: (j- temp): ways[j]: ways[j- temp]: ways[j] + ways[j- temp]:
20 20 0 ways[20] = 3 ways[0] = 1 ways[20] + ways[0]= 4
21 20 1 ways[21] = 0 ways[1] = 0 ways[21] + ways[1]= 0
22 20 2 ways[22] = 0 ways[2] = 0 ways[22] + ways[2]= 0
23 20 3 ways[23] = 0 ways[3] = 0 ways[23] + ways[3]= 0
24 20 4 ways[24] = 0 ways[4] = 0 ways[24] + ways[4]= 0
25 20 5 ways[25] = 3 ways[5] = 1 ways[25] + ways[5]= 4
26 20 6 ways[26] = 0 ways[6] = 0 ways[26] + ways[6]= 0
27 20 7 ways[27] = 0 ways[7] = 0 ways[27] + ways[7]= 0
28 20 8 ways[28] = 0 ways[8] = 0 ways[28] + ways[8]= 0
29 20 9 ways[29] = 0 ways[9] = 0 ways[29] + ways[9]= 0
30 20 10 ways[30] = 4 ways[10] = 2 ways[30] + ways[10]= 6
*****************************************************
i:0,w[i]: 1 i:1,w[i]: 0 i:2,w[i]: 0 i:3,w[i]: 0 i:4,w[i]: 0 i:5,w[i]: 1 i:6,w[i]: 0 i:7,w[i]: 0 i:8,w[i]: 0 i:9,w[i]: 0
i:10,w[i]: 2 i:11,w[i]: 0 i:12,w[i]: 0 i:13,w[i]: 0 i:14,w[i]: 0 i:15,w[i]: 2 i:16,w[i]: 0 i:17,w[i]: 0 i:18,w[i]: 0 i:19,w[i]: 0
i:20,w[i]: 4 i:21,w[i]: 0 i:22,w[i]: 0 i:23,w[i]: 0 i:24,w[i]: 0 i:25,w[i]: 4 i:26,w[i]: 0 i:27,w[i]: 0 i:28,w[i]: 0 i:29,w[i]: 0
i:30,w[i]: 6
