Your job is to paint a row of n houses red, green, or blue so as to minimize total cost, where cost(i, color) = cost to pain house i the specified color. You may not paint two adjacent houses the same color. Write a program to determine an optimal solution to the problem. Hint : Use bottom-up dynamic programming and solve the following subproblems for each i = 1, 2, …, n:

• red(i) = min cost to paint houses 1, 2, …, i so that the house i is red

• green(i) = min cost to paint houses 1, 2, …, i so that the house i is green

• blue(i) = min cost to paint houses 1, 2, …, i so that the house i is blue