Problem Statement: In DynamicLand the currency is made up of coins with the following values: 1, 2, 4 and 8. How many different ways can these coins be combined to make 17.
Solution:
This problem can be solved by forming a table, where the rows represent each of the different coin types and the columns represent the number of ways the value represented by the column number can be produced using coins of the row number or less.
In the above problem there will be 4 rows, one for each coin and 18 columns, 0 through 17.
Cell [*][0] will be 1, since there is only one way to reach the value of 0, regardless of the number and value of coins used.
Cell [0][*] will be 1 as well, any value can be made up using n of coins of one unit.
To compute the values in other cells
If the value for the coin associated with the row is greater than the current value, the coin can not be used.
You must use only coins of lower value.
So copy the value from the row above.
If the value of the coin associated with the row is less than or equal to the current value,
You can still use coins of lower values
But you could also use coins of this value.
Add the current value in the row above (not using this coin) to the ways to entry for this row where the value is less than the current coin.
For example entry[1][2] (coin value = 2, total value =2)