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

解法1：O(N*K) Time

N是房子的数量，K是房子的颜色数。
经典dp, dp[i][j] 表示前i个房子的最小cost,当第i个房子涂得颜色是j。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public int minCost(int[][] costs) {
        if (costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        int n = costs.length;
        int col = costs[0].length;
        int[][] dp = new int[n][col];   // first i houses painted and ith house painted with jth color
        for (int j = 0; j < col;j++) {
            dp[0][j] = costs[0][j];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < col; j++) {
                int temp = Integer.MAX_VALUE;
                for (int k = 0; k < col; k++) {
                    if (k != j) {
                        temp = Math.min(temp, dp[i - 1][k]);    
                    }
                }
                dp[i][j] = costs[i][j] + temp;
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < col; j++) {
            res = Math.min(res, dp[n - 1][j]);
        }
        return res;
    }
}