CareerCup

Solution using dynamic programing.
The solution is as folows (calc(int, int) function):
1. If a best solution was found, use it.
2. Select one color not forbiden;
3. Solve the problem for n-1 houses.
4. get the best result adding best result for n-1 to current cost.
5. see if it is the current minimum when you add current color cost
6. update minimum if needed.
7. save best result.

Time complexity: Colors*Houses.
Space complexity: Colors*Houses.
Is easy to see it, if you realize that the runtime cost is the time to fill the best solution matrix, sized Colors*Houses.
By the way, for the problem stated above, the solution is:
Colors: [1, 0, 2, 1, 0, 1] (G, R, B, G, R, G)
Cost: 18

public class PaintHouse {
	public class BestResult {
		public int[] colors;
		public int cost;
		public BestResult(int[] colors, int cost) {
			this.colors = colors;
			this.cost = cost;
		}
		
	}	
	private int[][] cost;
	private BestResult[][] best;	
	public PaintHouse(int[][] cost) {
		this.cost = cost;
		this.best = new BestResult[cost.length][cost[0].length];
	}	
	public BestResult calc() {
		return calc(cost[0].length, -1);
	}
	private BestResult calc(int n, int forbiden) {
		if (forbiden >= 0 && best[forbiden][n-1] != null)
			return best[forbiden][n-1];
		BestResult min = null;
		for (int c = 0, h = cost[0].length - n; c< cost.length; ++c) {
			if (c != forbiden) {
				 if (n == 1) {
					 if (min == null || min.cost > cost[c][h]) {
						 min = new BestResult(new int[] {c}, cost[c][h]);
					 }
				 } else {
					 BestResult next = calc(n-1, c);
					 if (min == null 
                                            || min.cost > (next.cost + cost[c][h])) {
						 min = new BestResult(new int[next.colors.length+1], 
                                                   next.cost + cost[c][h]);
						 min.colors[0] = c;
						 System.arraycopy(next.colors, 0, 
                                                  min.colors, 1, next.colors.length);
					 }
				 }
			}
		}
		if (forbiden >= 0)
			best[forbiden][n-1] = min;
		return min;
	}

}
public class PaintHouseTest {
	@Test
	public void testCalc() {
		int[][] cost = new int[][] { 
				new int[] { 7, 3, 8, 6, 1, 2},
				new int[] { 5, 6, 7, 2, 4, 3},
				new int[] {10, 1, 4, 9, 7, 6}
		};
		PaintHouse calc = new PaintHouse(cost);
		BestResult bestResult = calc.calc();
		System.out.println("Colors: " + Arrays.toString(bestResult.colors));
		System.out.println("Cost: " + bestResult.cost);
		assertEquals(bestResult.cost, 18);
	}

}

If T(i) is the min up to the ith place, and T(i,j) is the min up to ith place with ith spot having the color j, then:

T(i)=min(T(i-1,B)+min(Gi,Ri), T(i-1,R)+min(Gi,Bi), T(i-1,G)+min(Bi,Ri))

which naively would result in exponential growth, but if you cache the results in an array, I believe it should be O(n).

dp,
dp[i][j] = minimum cost of painting 0,1,....,i using color j

class Paint
{
int[] Red = { 7, 3, 8 , 6, 1, 2 };
int[] Green = { 9, 6, 7, 2, 4, 3 };
int[] Blue = { 2, 1, 4, 9, 7, 6 };


public Paint()
{
int minR = MinRed(Red.Length - 1);
int minG = MinGreen(Green.Length - 1);
int minB = MinBlue(Blue.Length - 1);

int minimum = Min(minR, Min(minB, minG));

}

int Min(int a, int b)
{
return a < b ? a : b;
}

int MinRed(int N)
{
if (N < 0)
return 0;
else
return Red[N] + Min(MinGreen(N - 1), MinBlue(N - 1));
}

int MinGreen(int N)
{
if (N < 0)
return 0;
else
return Green[N] + Min(MinRed(N - 1), MinBlue(N - 1));
}

int MinBlue(int N)
{
if (N < 0)
return 0;
else
return Blue[N] + Min(MinGreen(N - 1), MinRed(N - 1));
}

}

@lucas can u explain ur solution little bit more by taking values say for 3 houses

DP Solution -

At each row, you take current color + min(previous another colors)

T(n) = costR[n]+ min(dp[n-1][G],dp[n-1][B])

private static int minCost(int[][] cost) {
        int n = cost[0].length;
        int m = cost.length;

        int[][] dp = new int[n][m];

        for (int i = 0; i < m; i++) {
            dp[0][i] = cost[i][0];
        }

        for (int i = 1; i < n; i++) {

            for (int j = 0; j < m; j++) {

                // Red
                if (j == 0) {
                    dp[i][j] = cost[j][i] + Math.min(dp[i - 1][1], dp[i - 1][2]);
                }
                //Green
                else if (j == 1) {
                    dp[i][j] = cost[j][i] + Math.min(dp[i - 1][0], dp[i - 1][2]);
                }
                //Blue
                else if (j == 2) {
                    dp[i][j] = cost[j][i] + Math.min(dp[i - 1][0], dp[i - 1][1]);
                }
            }
        }
        return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
    }

const COSTS = [ //COSTS[color][house]

//HOUSE  1 2 3 4 5 6
        [1,2,3,4,5,1], // Red
        [1,3,4,5,1,2], // Blue
        [1,4,5,9,1,3], // Green
        [2,3,5,4,1,3]  // Yellow
];

function * paintHouse(costs, house = 0, total = 0, excludeColor){
  if (house === costs[0].length) {
    yield total;
    return;
  } 
  for (let color = 0; color < costs.length; color++){
    if (color !== excludeColor) yield * paintHouse(costs, house+1, total + costs[color][house], color);
  }

}

console.log(Math.min(...paintHouse(COSTS)));