Leetcode: Paint House

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.

Show Company Tags
Show Tags
Show Similar Problems

 1 public class Solution {
 2     public int minCost(int[][] costs) {
 3         if (costs==null || costs.length==0 || costs[0].length==0) return 0;
 4         int n = costs.length;
 5         int c = costs[0].length;
 6         int[][] res = new int[n][c];
 7         //Arrays.fill(res, Integer.MAX_VALUE);
 8         for (int i=0; i<n; i++) {
 9             for (int j=0; j<c; j++) {
10                 res[i][j] = Integer.MAX_VALUE;
11             }
12         }
13         for (int j=0; j<c; j++) {
14             res[0][j] = costs[0][j];
15         }
16         for (int i=1; i<n; i++) {
17             for (int j=0; j<c; j++) {
18                 for (int k=0; k<c; k++) {
19                     res[i][j] = (k==j)? res[i][j] : Math.min(res[i][j], res[i-1][k]+costs[i][j]);
20                 }
21             }
22         }
23         int result = Integer.MAX_VALUE;
24         for (int j=0; j<c; j++) {
25             result = Math.min(result, res[n-1][j]);
26         }
27         return result;
28     }
29 }