We describe an efficient dynamic programming algorithm to compute the number of ways that one might make change for a dollar. The answer, assuming pennies, nickles, dimes, quarters, and half-dollars? Two hundred ninety two.

Change for a Dollar

The key idea of dynamic programming is to construct a current solution from previously computed solutions. In this case, we consider solutions to exist for each value less than the current. So, for $1, we assume that we know solutions for 99 cents, 98 cents, etc. Here, a solution is a collection of vectors with the number of each type of coin in each component. For example, (4,0,2,1,1) is 4 pennies, 0 nickles, 2 dimes, 1 quarter, and 1 half dollar and has value 99 cents. (4,0,2,1,1) is one of many ways in which one might make change for 99 cents.

Returning to the case of $1, we ask which previous solutions are applicable. If we have a solution for 99 cents, then we could add a penny to each of the tuples in the collection for 99 cents. If we have a solution for 95 cents, then we could add a nickle to each of the tuples in the collection for 95 cents. In fact, for a $1, we are interested in previous solutions that look back by the amount of a single coin: 99 cents (lookback one penny), 95 cents (lookback one nickle), 90 cents (lookback one dime), 75 cents (lookback one quarter), and 50 cents (lookback one half-dollar).

The current solution, then, is to consider each tuple from the applicable lookbacks and add the respective coin. However, this can result in duplicate tuples. Consider making change for 6 cents using this approach. The applicable lookbacks are a penny and a nickle. The penny lookback uses each 5 cent tuple and adds a penny: (5,0,0,0,0) + (1,0,0,0,0) and (0,1,0,0,0) + (1,0,0,0,0). The nickle lookback uses each 1 cent tuple and adds a nickle: (1,0,0,0,0) + (0,1,0,0,0). This produces (6,0,0,0,0), (1,1,0,0,0), and (1,1,0,0,0). If we reduce this to unique tuples, we get the expected solution for 6 cents: there are two tuples and they are (6,0,0,0,0) and (1,1,0,0,0). In the code, we use a binary tree to enforce uniqueness.

main.c

This defines the auxiliary variables and computes increasingly larger-value solutions.

Why write in C? For practice.

/assets/2016-10-06-change-for-a-dollar/main.c:

/*
 * main.c
 *
 *  Created on: Oct 6, 2016
 *      Author: Dustin Lennon
 *      Email:  dustin@inferentialist.com
 */

#include <stdio.h>

#include "soln.h"
#include "coin_vec.h"

/* function prototypes */
void cv_tree_node_to_soln(soln_t* s, cv_tree_node_t* node);

int main(int argc, char** argv)
{
    int i,j,k;
    int lookback;

    // Denomination of each coin
    coin_vec_t values, tmp_cv;
    set_coin_vec(&values, 1, 5, 10, 25, 50);

    // Indicator functions: used to add a particular coin to a previous coin_vec
    coin_vec_t coin_ind[NCOINS];
    set_coin_vec(&coin_ind[0], 1, 0, 0, 0, 0);
    set_coin_vec(&coin_ind[1], 0, 1, 0, 0, 0);
    set_coin_vec(&coin_ind[2], 0, 0, 1, 0, 0);
    set_coin_vec(&coin_ind[3], 0, 0, 0, 1, 0);
    set_coin_vec(&coin_ind[4], 0, 0, 0, 0, 1);

    // coin_vec tree: maintains unique coin_vecs
    cv_tree_t cv_tree;
    cv_tree_init(&cv_tree);

    // how far should we go?  100 == $1
    const int sz = 100;

    /* create and initialize the solutions array */
    soln_t soln[sz+1];
    for(i=0; i<=sz; i++)
    {
        init_soln(&soln[i]);
    }

    /* initialize the base-case */
    malloc_soln(&soln[0], 1);
    set_coin_vec(&(soln[0].p_coin_vec[0]), 0, 0, 0, 0, 0);

    /* loop through each value between 0 cents and 'sz' cents */
    for(i=1; i<=sz; i++)
    {
        /* the current solution uses several previous solutions; in particular, solutions
         * associated with values that are one coin-value behind, e.g. [26] would combine
         * solutions from [25], [21], [16], [1] */
        for(j=0; j<NCOINS; j++)
        {
            lookback = values.counts[j];
            if( i - lookback >= 0 )
            {
                /* for each previous solution, add the respective coin to bring the value up
                 * to the current level; keep the unique coin_vec's
                 */
                soln_t* s = &soln[ i - lookback ];
                for(k=0; k < s->nrow; k++)
                {
                    add_coin_vec(&tmp_cv, &(s->p_coin_vec[k]), &coin_ind[j]);
                    cv_tree_insert(&cv_tree, &tmp_cv);
                }
            }
        }

        /* copy from the tree to the array */
        malloc_soln(&soln[i], cv_tree.count);
        cv_tree_node_to_soln(&soln[i], cv_tree.root);

        /* print out the intermediate solution */
        printf("%d (%d):\n", i, soln[i].nrow);
        print_soln(&soln[i]);
        printf("\n");

        cv_tree_empty(&cv_tree);
    }

    /* clean up dynamically allocated memory */
    free_soln(&soln[0]);
    for(i=0; i<=sz; i++)
    {
        free_soln(&soln[i]);
    }

    return 0;
}

/* recursive function to transfer the coin_vecs from the tree to the current soln */
void cv_tree_node_to_soln(soln_t* s, cv_tree_node_t* node)
{
    if(node == NULL)
        return;
    cv_tree_node_to_soln(s, node->l);
    cv_tree_node_to_soln(s, node->r);

    int idx = node->idx;
    copy_coin_vec( &(s->p_coin_vec[idx]), &(node->cv) );
}

coin_vec.[ch]

These files define the coin-count tuples and provide helper functions for manipulating them. The cv_tree_t struct is a binary tree that stores unique tuples.

/assets/2016-10-06-change-for-a-dollar/coin_vec.h:

/*
 * coinvec.h
 *
 *  Created on: Oct 6, 2016
 *      Author: Dustin Lennon
 *      Email:  dustin@inferentialist.com
 */

#ifndef COINVEC_H_
#define COINVEC_H_

#define NCOINS 5

typedef struct
{
    /* penny, nickel, dime, quarter, half-dollar */
    int counts[NCOINS];
} coin_vec_t;

void set_coin_vec(coin_vec_t* src, int p, int n, int d, int q, int hd);
void copy_coin_vec(coin_vec_t* dest, coin_vec_t* src);
void add_coin_vec(coin_vec_t* dest, coin_vec_t* src, coin_vec_t* inc);
int cmp_coin_vec(coin_vec_t* lhs, coin_vec_t* rhs);

typedef struct cv_tree_node_t cv_tree_node_t;
typedef struct cv_tree_t cv_tree_t;

/* wrapper object for coin_vec tree */
struct cv_tree_t
{
    cv_tree_node_t* root;
    int count;
};

/* internal data structure for tree */
struct cv_tree_node_t
{
    cv_tree_node_t* l, *r;
    coin_vec_t cv;

    /* idx:  a unique id for each node added to the tree */
    int idx;
};

void cv_tree_init(cv_tree_t* t);
void cv_tree_insert(cv_tree_t* t, coin_vec_t* cv);
void cv_tree_empty(cv_tree_t* t);

cv_tree_node_t* cv_tree_node_new(coin_vec_t* cv, int* idx);
cv_tree_node_t* cv_tree_node_insert(cv_tree_node_t* node, coin_vec_t* cv, int* idx);
void cv_tree_node_empty(cv_tree_node_t* node);



#endif /* COINVEC_H_ */

/assets/2016-10-06-change-for-a-dollar/coin_vec.c:

/*
 * coin_vec.c
 *
 *  Created on: Oct 6, 2016
 *      Author: Dustin Lennon
 *      Email:  dustin@inferentialist.com
 */

#include <stdlib.h>

#include "coin_vec.h"

#define PENNY 0
#define NICKEL 1
#define DIME 2
#define QUARTER 3
#define HALFDOLLAR 4

/* Set the coin vector.
 * NOTE - this should be the only place in the code where the
 * coin counts are set individually.  */
void set_coin_vec(coin_vec_t* src, int p, int n, int d, int q, int hd)
{
    src->counts[PENNY] = p;
    src->counts[NICKEL] = n;
    src->counts[DIME] = d;
    src->counts[QUARTER] = q;
    src->counts[HALFDOLLAR] = hd;
}

/* Copy a coin_vec from src to dest */
void copy_coin_vec(coin_vec_t* dest, coin_vec_t* src)
{
    for(int i=0; i<NCOINS; i++)
    {
        dest->counts[i] = src->counts[i];
    }
}

/* Add a coin_vec to src and store in dest */
void add_coin_vec(coin_vec_t* dest, coin_vec_t* src, coin_vec_t* inc)
{
    for(int i=0; i<NCOINS; i++)
    {
        dest->counts[i] = src->counts[i] + inc->counts[i];
    }
}

/* Comparison function for two coin vectors */
int cmp_coin_vec(coin_vec_t* lhs, coin_vec_t* rhs)
{
    for(int i=0; i<NCOINS; i++)
    {
        if(lhs->counts[i] < rhs->counts[i])
            return -1;
        if(lhs->counts[i] > rhs->counts[i])
            return 1;
    }
    return 0;
}

/* initialize the coin_vec tree */
void cv_tree_init(cv_tree_t* t)
{
    t->count = 0;
    t->root = NULL;
}

/* insert a coin_vec into the tree (wrapper) */
void cv_tree_insert(cv_tree_t* t, coin_vec_t* cv)
{
    t->root = cv_tree_node_insert(t->root, cv, &(t->count));
}

/* clean up the tree and free the underlying memory (wrapper) */
void cv_tree_empty(cv_tree_t* t)
{
    cv_tree_node_empty(t->root);
    t->count = 0;
    t->root = NULL;
}

/* create a new node in the tree, set the coin_vec, and an index */
cv_tree_node_t* cv_tree_node_new(coin_vec_t* cv, int* idx)
{
    cv_tree_node_t* node = (cv_tree_node_t*) malloc(sizeof(cv_tree_node_t));
    copy_coin_vec(&(node->cv), cv);

    node->idx = *idx;

    /* bump the index; it's a pointer to the tree->count */
    *idx = *idx + 1;

    node->l = NULL;
    node->r = NULL;

    return node;
}

/* recursively insert a coin_vec into the tree */
cv_tree_node_t* cv_tree_node_insert(cv_tree_node_t* node, coin_vec_t* cv, int* idx)
{
    if(node == NULL)
    {
        return cv_tree_node_new(cv, idx);
    }

    int cmp = cmp_coin_vec(&node->cv, cv);
    if( cmp == -1 )
    {
        node->l = cv_tree_node_insert(node->l, cv, idx);
    }
    else if (cmp == 1)
    {
        node->r = cv_tree_node_insert(node->r, cv, idx);
    }

    return node;
}

/* recursively clean up the tree */
void cv_tree_node_empty(cv_tree_node_t* node)
{
    if(node == NULL)
        return;

    cv_tree_node_empty(node->l);
    cv_tree_node_empty(node->r);
    free(node);
}

soln.[ch]

These files define the soln_t struct and helper functions.

/assets/2016-10-06-change-for-a-dollar/soln.h:

/*
 * soln.h
 *
 *  Created on: Oct 6, 2016
 *      Author: Dustin Lennon
 *      Email:  dustin@inferentialist.com
 */

#ifndef SOLN_H_
#define SOLN_H_

#include "coin_vec.h"

typedef struct
{
    coin_vec_t* p_coin_vec;
    int nrow;
} soln_t;

void print_soln(soln_t* s);
void init_soln(soln_t* s);
void malloc_soln(soln_t* s, int nrow);
void free_soln(soln_t* s);


#endif /* SOLN_H_ */

/assets/2016-10-06-change-for-a-dollar/soln.c:

/*
 * soln.c
 *
 *  Created on: Oct 6, 2016
 *      Author: Dustin Lennon
 *      Email:  dustin@inferentialist.com
 */

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>

#include "coin_vec.h"
#include "soln.h"

/* print a solution */
void print_soln(soln_t* s)
{
    int nrow = s->nrow;
    for(int i=0; i<nrow; i++)
    {
        coin_vec_t* cv = &(s->p_coin_vec[i]);
        printf("(%d", cv->counts[0]);
        for(int j=1; j<NCOINS; j++)
        {
            printf(",%d", cv->counts[j]);
        }
        printf(")\n");
    }
}

/* initialize a solution */
void init_soln(soln_t* s)
{
    s->nrow = 0;
    s->p_coin_vec = NULL;
}

/* allocate the memory for nrow coin_vec tuples */
void malloc_soln(soln_t* s, int nrow)
{
    if(s->p_coin_vec != NULL)
    {
        assert("error:  malloc'd a soln_t that was already malloc'd");
    }

    s->p_coin_vec = (coin_vec_t*) malloc(nrow * sizeof(coin_vec_t));
    s->nrow = nrow;
    for(int i=0; i<nrow; i++)
    {
        memset(s->p_coin_vec[i].counts, 0, NCOINS * sizeof(int));
    }
}

/* free the memory for the coin_vec tuples */
void free_soln(soln_t* s)
{
    if(s->p_coin_vec == NULL)
    {
        assert("error:  free'd a soln_t that was never malloc'd");
    }

    free(s->p_coin_vec);

    s->nrow = 0;
    s->p_coin_vec = NULL;
}

Dollar Tuples

These tuples are coin counts of the form (pennies, nickles, dimes, quarters, half-dollars).

  1. (100,0,0,0,0)
  2. (95,1,0,0,0)
  3. (90,2,0,0,0)
  4. (90,0,1,0,0)
  5. (85,3,0,0,0)
  6. (85,1,1,0,0)
  7. (80,4,0,0,0)
  8. (80,2,1,0,0)
  9. (80,0,2,0,0)
  10. (75,5,0,0,0)
  11. (75,3,1,0,0)
  12. (75,1,2,0,0)
  13. (75,0,0,1,0)
  14. (70,6,0,0,0)
  15. (70,4,1,0,0)
  16. (70,2,2,0,0)
  17. (70,1,0,1,0)
  18. (70,0,3,0,0)
  19. (65,7,0,0,0)
  20. (65,5,1,0,0)
  21. (65,3,2,0,0)
  22. (65,2,0,1,0)
  23. (65,1,3,0,0)
  24. (65,0,1,1,0)
  25. (60,8,0,0,0)
  26. (60,6,1,0,0)
  27. (60,4,2,0,0)
  28. (60,3,0,1,0)
  29. (60,2,3,0,0)
  30. (60,1,1,1,0)
  31. (60,0,4,0,0)
  32. (55,9,0,0,0)
  33. (55,7,1,0,0)
  34. (55,5,2,0,0)
  35. (55,4,0,1,0)
  36. (55,3,3,0,0)
  37. (55,2,1,1,0)
  38. (55,1,4,0,0)
  39. (55,0,2,1,0)
  40. (50,10,0,0,0)
  41. (50,8,1,0,0)
  42. (50,6,2,0,0)
  43. (50,5,0,1,0)
  44. (50,4,3,0,0)
  45. (50,3,1,1,0)
  46. (50,2,4,0,0)
  47. (50,1,2,1,0)
  48. (50,0,5,0,0)
  49. (50,0,0,2,0)
  50. (50,0,0,0,1)
  51. (45,11,0,0,0)
  52. (45,9,1,0,0)
  53. (45,7,2,0,0)
  54. (45,6,0,1,0)
  55. (45,5,3,0,0)
  56. (45,4,1,1,0)
  57. (45,3,4,0,0)
  58. (45,2,2,1,0)
  59. (45,1,5,0,0)
  60. (45,1,0,2,0)
  61. (45,1,0,0,1)
  62. (45,0,3,1,0)
  63. (40,12,0,0,0)
  64. (40,10,1,0,0)
  65. (40,8,2,0,0)
  66. (40,7,0,1,0)
  67. (40,6,3,0,0)
  68. (40,5,1,1,0)
  69. (40,4,4,0,0)
  70. (40,3,2,1,0)
  71. (40,2,5,0,0)
  72. (40,2,0,2,0)
  73. (40,2,0,0,1)
  74. (40,1,3,1,0)
  75. (40,0,6,0,0)
  76. (40,0,1,2,0)
  77. (40,0,1,0,1)
  78. (35,13,0,0,0)
  79. (35,11,1,0,0)
  80. (35,9,2,0,0)
  81. (35,8,0,1,0)
  82. (35,7,3,0,0)
  83. (35,6,1,1,0)
  84. (35,5,4,0,0)
  85. (35,4,2,1,0)
  86. (35,3,5,0,0)
  87. (35,3,0,2,0)
  88. (35,3,0,0,1)
  89. (35,2,3,1,0)
  90. (35,1,6,0,0)
  91. (35,1,1,2,0)
  92. (35,1,1,0,1)
  93. (35,0,4,1,0)
  94. (30,14,0,0,0)
  95. (30,12,1,0,0)
  96. (30,10,2,0,0)
  97. (30,9,0,1,0)
  98. (30,8,3,0,0)
  99. (30,7,1,1,0)
  100. (30,6,4,0,0)
  101. (30,5,2,1,0)
  102. (30,4,5,0,0)
  103. (30,4,0,2,0)
  104. (30,4,0,0,1)
  105. (30,3,3,1,0)
  106. (30,2,6,0,0)
  107. (30,2,1,2,0)
  108. (30,2,1,0,1)
  109. (30,1,4,1,0)
  110. (30,0,7,0,0)
  111. (30,0,2,2,0)
  112. (30,0,2,0,1)
  113. (25,15,0,0,0)
  114. (25,13,1,0,0)
  115. (25,11,2,0,0)
  116. (25,10,0,1,0)
  117. (25,9,3,0,0)
  118. (25,8,1,1,0)
  119. (25,7,4,0,0)
  120. (25,6,2,1,0)
  121. (25,5,5,0,0)
  122. (25,5,0,2,0)
  123. (25,5,0,0,1)
  124. (25,4,3,1,0)
  125. (25,3,6,0,0)
  126. (25,3,1,2,0)
  127. (25,3,1,0,1)
  128. (25,2,4,1,0)
  129. (25,1,7,0,0)
  130. (25,1,2,2,0)
  131. (25,1,2,0,1)
  132. (25,0,5,1,0)
  133. (25,0,0,3,0)
  134. (25,0,0,1,1)
  135. (20,16,0,0,0)
  136. (20,14,1,0,0)
  137. (20,12,2,0,0)
  138. (20,11,0,1,0)
  139. (20,10,3,0,0)
  140. (20,9,1,1,0)
  141. (20,8,4,0,0)
  142. (20,7,2,1,0)
  143. (20,6,5,0,0)
  144. (20,6,0,2,0)
  145. (20,6,0,0,1)
  146. (20,5,3,1,0)
  147. (20,4,6,0,0)
  148. (20,4,1,2,0)
  149. (20,4,1,0,1)
  150. (20,3,4,1,0)
  151. (20,2,7,0,0)
  152. (20,2,2,2,0)
  153. (20,2,2,0,1)
  154. (20,1,5,1,0)
  155. (20,1,0,3,0)
  156. (20,1,0,1,1)
  157. (20,0,8,0,0)
  158. (20,0,3,2,0)
  159. (20,0,3,0,1)
  160. (15,17,0,0,0)
  161. (15,15,1,0,0)
  162. (15,13,2,0,0)
  163. (15,12,0,1,0)
  164. (15,11,3,0,0)
  165. (15,10,1,1,0)
  166. (15,9,4,0,0)
  167. (15,8,2,1,0)
  168. (15,7,5,0,0)
  169. (15,7,0,2,0)
  170. (15,7,0,0,1)
  171. (15,6,3,1,0)
  172. (15,5,6,0,0)
  173. (15,5,1,2,0)
  174. (15,5,1,0,1)
  175. (15,4,4,1,0)
  176. (15,3,7,0,0)
  177. (15,3,2,2,0)
  178. (15,3,2,0,1)
  179. (15,2,5,1,0)
  180. (15,2,0,3,0)
  181. (15,2,0,1,1)
  182. (15,1,8,0,0)
  183. (15,1,3,2,0)
  184. (15,1,3,0,1)
  185. (15,0,6,1,0)
  186. (15,0,1,3,0)
  187. (15,0,1,1,1)
  188. (10,18,0,0,0)
  189. (10,16,1,0,0)
  190. (10,14,2,0,0)
  191. (10,13,0,1,0)
  192. (10,12,3,0,0)
  193. (10,11,1,1,0)
  194. (10,10,4,0,0)
  195. (10,9,2,1,0)
  196. (10,8,5,0,0)
  197. (10,8,0,2,0)
  198. (10,8,0,0,1)
  199. (10,7,3,1,0)
  200. (10,6,6,0,0)
  201. (10,6,1,2,0)
  202. (10,6,1,0,1)
  203. (10,5,4,1,0)
  204. (10,4,7,0,0)
  205. (10,4,2,2,0)
  206. (10,4,2,0,1)
  207. (10,3,5,1,0)
  208. (10,3,0,3,0)
  209. (10,3,0,1,1)
  210. (10,2,8,0,0)
  211. (10,2,3,2,0)
  212. (10,2,3,0,1)
  213. (10,1,6,1,0)
  214. (10,1,1,3,0)
  215. (10,1,1,1,1)
  216. (10,0,9,0,0)
  217. (10,0,4,2,0)
  218. (10,0,4,0,1)
  219. (5,19,0,0,0)
  220. (5,17,1,0,0)
  221. (5,15,2,0,0)
  222. (5,14,0,1,0)
  223. (5,13,3,0,0)
  224. (5,12,1,1,0)
  225. (5,11,4,0,0)
  226. (5,10,2,1,0)
  227. (5,9,5,0,0)
  228. (5,9,0,2,0)
  229. (5,9,0,0,1)
  230. (5,8,3,1,0)
  231. (5,7,6,0,0)
  232. (5,7,1,2,0)
  233. (5,7,1,0,1)
  234. (5,6,4,1,0)
  235. (5,5,7,0,0)
  236. (5,5,2,2,0)
  237. (5,5,2,0,1)
  238. (5,4,5,1,0)
  239. (5,4,0,3,0)
  240. (5,4,0,1,1)
  241. (5,3,8,0,0)
  242. (5,3,3,2,0)
  243. (5,3,3,0,1)
  244. (5,2,6,1,0)
  245. (5,2,1,3,0)
  246. (5,2,1,1,1)
  247. (5,1,9,0,0)
  248. (5,1,4,2,0)
  249. (5,1,4,0,1)
  250. (5,0,7,1,0)
  251. (5,0,2,3,0)
  252. (5,0,2,1,1)
  253. (0,20,0,0,0)
  254. (0,18,1,0,0)
  255. (0,16,2,0,0)
  256. (0,15,0,1,0)
  257. (0,14,3,0,0)
  258. (0,13,1,1,0)
  259. (0,12,4,0,0)
  260. (0,11,2,1,0)
  261. (0,10,5,0,0)
  262. (0,10,0,2,0)
  263. (0,10,0,0,1)
  264. (0,9,3,1,0)
  265. (0,8,6,0,0)
  266. (0,8,1,2,0)
  267. (0,8,1,0,1)
  268. (0,7,4,1,0)
  269. (0,6,7,0,0)
  270. (0,6,2,2,0)
  271. (0,6,2,0,1)
  272. (0,5,5,1,0)
  273. (0,5,0,3,0)
  274. (0,5,0,1,1)
  275. (0,4,8,0,0)
  276. (0,4,3,2,0)
  277. (0,4,3,0,1)
  278. (0,3,6,1,0)
  279. (0,3,1,3,0)
  280. (0,3,1,1,1)
  281. (0,2,9,0,0)
  282. (0,2,4,2,0)
  283. (0,2,4,0,1)
  284. (0,1,7,1,0)
  285. (0,1,2,3,0)
  286. (0,1,2,1,1)
  287. (0,0,10,0,0)
  288. (0,0,5,2,0)
  289. (0,0,5,0,1)
  290. (0,0,0,4,0)
  291. (0,0,0,2,1)
  292. (0,0,0,0,2)