### 题目

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note: All costs are positive integers.

### DFS(回溯)

#### 代码

public class Solution {
public int minCost(int[][] costs) {
int[] minCost = new int[]{-1};
dfs(costs,0,-1,0,minCost);
return minCost[0];
}
public void dfs(int[][] costs, int row, int col, int costSoFar, int[] minCost) {
if (row == costs.length) { minCost[0] = (minCost[0] < 0)? costSoFar : Math.min(minCost[0],costSoFar); return; }
for (int i = 0; i < costs[0].length; i++) {
if (col >= 0 && i == col) {  continue; }
dfs(costs,row+1,i,costSoFar+costs[row][i],minCost);
}
}
}


### 自底向上的动态规划

              红  黄   蓝



              红  黄   蓝



#### 代码

public class Solution {
public int minCost(int[][] costs) {
if (costs.length == 0) { return 0; }
dp(costs,0);
return Math.min(Math.min(costs[0][0],costs[0][1]),costs[0][2]);
}
public void dp(int[][] costs, int row) {
if (row == costs.length-1) { return; }
dp(costs,row+1);
costs[row][0] += Math.min(costs[row+1][1],costs[row+1][2]);
costs[row][1] += Math.min(costs[row+1][0],costs[row+1][2]);
costs[row][2] += Math.min(costs[row+1][0],costs[row+1][1]);
}
}