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. }

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.