Thursday, February 19, 2009

Coin changes and dynamic programming

Coin Change is the problem of finding different ways of making changes for a particular amount of cents, n, having an infinite amount of coins available. For instance, how can you change 10 dollars having an infinite amount of nickels (1 cent), pennies (5 cents), quarter (10 cents), dimes (25 cents), one dollars?

Well this is the typical problem that you can solve by using dynamic programming.

1 comment:

  1. The problem can be formulated as it follows: Given a set of coins S_k = { C1, ... Ck } find w_k such that the available amount of moneys N is equal to the weighted sum of the coins:

    N = \sum_i=1..k w_i * Ci

    The problem shows the optimal sub-structure typical of dynamic programming.

    If a solution does not contain the coin Ck, then we can resolve the sub-problem [N, S_{k-1} = { C1, .... C_{k-1}}]

    If a solution does contain the coin Ck, then we can resolve the sub-problem [N-Ck, S_{k} = {C1, ...., Ck}]

    So that we have the recurrence

    C(N, M) = C(N, M-1) + C(N-C_k, M)

    with boundary conditions

    C(N, M) = 0 , N >=0, M <= 0;
    C(N, M) = 0 , N <= 0

    This problem can be solved in O(nm) with dynamic programming. As usual, you can save some computations using memoization.