# Paint a row of houses with the minimum cost

## Paint a row of houses with the minimum cost

There are a row of houses. Each house can be painted with three colors: red, blue and green. The cost of painting each house with a certain color is different. No two adjacent houses have the same color. Paint the houses with the minimum cost.

A dynamic programming solution in C:

1. `#include <limits.h>`
2. `#include <stdio.h>`
3. ` `
4. `typedef enum {`
5. `  RED, GREEN, BLUE, NONE`
6. `} color_t;`
7. ` `
8. `typedef struct {`
9. `  int red;`
10. `  int green;`
11. `  int blue;`
12. `} price_t;`
13. ` `
14. `int paint(color_t *output, const price_t *input`
15. `      , const int n, const color_t last_color) {`
16. `  if(0 == n) {`
17. `    return 0;`
18. `  } else {`
19. `    const int i = n - 1;`
20. `    const int red_cost = RED == last_color ? INT_MAX`
21. `      : input[i].red + paint(output, input, n - 1, RED);`
22. `    const int green_cost = GREEN == last_color ? INT_MAX`
23. `      : input[i].green + paint(output, input, n - 1, GREEN);`
24. `    const int blue_cost = BLUE == last_color ? INT_MAX`
25. `      : input[i].blue + paint(output, input, n - 1, BLUE);`
26. `    output[i] = red_cost < green_cost`
27. `      ? (red_cost < blue_cost ? RED : BLUE)`
28. `      : (green_cost < blue_cost ? GREEN : BLUE);`
29. `    switch(output[i]) {`
30. `      case RED: return red_cost;`
31. `      case GREEN: return green_cost;`
32. `      case BLUE: return blue_cost;`
33. `      default: return 0;`
34. `    }`
35. `  }`
36. `}`
37. ` `
38. `int main(void) {`
39. `  color_t output[6];`
40. `  price_t input[6] = {`
41. `    {.red = 7, .green = 5, .blue = 10},`
42. `    {.red = 3, .green = 6, .blue = 1},`
43. `    {.red = 8, .green = 7, .blue = 4},`
44. `    {.red = 6, .green = 2, .blue = 9},`
45. `    {.red = 1, .green = 4, .blue = 7},`
46. `    {.red = 2, .green = 3, .blue = 6},`
47. `  };`
48. `  printf("min_cost=%d.\n", paint(output, input, 6, NONE)); // 18`
49. `  return 0;`
50. `}`