Question

Formatted question description: https://leetcode.ca/all/256.html

 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.


 Example:

 Given costs = [[14,2,11],[11,14,5],[14,3,10]]
 return 10

 house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10


 Note:
 All costs are positive integers.

Algorithm

Two-dimensional dynamic array dp, where dp[i][j] represents the minimum cost of brushing to the i+1th house with color j, and the state transition equation is:

dp[i][j] = cost[i][j] + min(dp[i-1][(j + 1)% 3], dp[i-1][(j + 2)% 3])

Code

Java

public class Paint_House {

    public class Solution {
        public int minCost(int[][] costs) {
            int len = costs.length;

            if(costs != null && len == 0) {
                return 0;
            }

            int[][] dp = costs; // dp[i][j], for house-i, three colors j (0 or 1 or 2)

            // no need dp[m+1][n+1], just i=1 is good enough
            for(int i = 1; i < len; i++){
                dp[i][0] = costs[i][0] + Math.min(costs[i - 1][1], costs[i - 1][2]);
                dp[i][1] = costs[i][1] + Math.min(costs[i - 1][0], costs[i - 1][2]);
                dp[i][2] = costs[i][2] + Math.min(costs[i - 1][0], costs[i - 1][1]);
            }

            return Math.min(dp[len - 1][0], Math.min(dp[len - 1][1], dp[len - 1][2]));
        }
    }
}

All Problems

All Solutions