• + 3 comments

    The solution to this problem is a good example of an efficient and tight Dynamic Programming algorithm. For those of you who are struggling with it, here's a tip. The number of ways you can make change for n using only the first m coins can be calculated using:

    (1) the number of ways you can make change for n using only the first m-1 coins.

    (2) the number of ways you can make change for n-C[m] using the first m coins (where C is the array of coins).

    This data allows you to build the recurrence relation.