Simple java DP solution

  • 96

    The 1st row is the prices for the 1st house, we can change the matrix to present sum of prices from the 2nd row. i.e, the costs[1][0] represent minimum price to paint the second house red plus the 1st house.

    public class Solution {
    public int minCost(int[][] costs) {
            return 0;
        for(int i=1; i<costs.length; i++){
            costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
        int n = costs.length-1;
        return Math.min(Math.min(costs[n][0], costs[n][1]), costs[n][2]);


  • 69

    Hi, yao9208. Great code! Very nice idea to give costs[i][j] a new meaning and at the mean time save the usage of additional spaces.

    Well, personally I would like to keep costs unmodified. I rewrite the code in C++, a little verbose than yours :-)

    class Solution {
        int minCost(vector<vector<int>>& costs) {
            if (costs.empty()) return 0;
            int n = costs.size(), r = 0, g = 0, b = 0;
            for (int i = 0; i < n; i++) {
                int rr = r, bb = b, gg = g; 
                r = costs[i][0] + min(bb, gg);
                b = costs[i][1] + min(rr, gg);
                g = costs[i][2] + min(rr, bb);
            return min(r, min(b, g));

    r/b/g in the i-th loop means the minimum costs to paint the i-th house in red/blue/green respectively plus painting the previous houses. The time and space complexities are still of O(n) and O(1).

  • 0

    It is nicer if you take "int n = costs.length-1;" before for loop and in the for loop use it as "i <= n;" :)

  • 1
    R's answer seems better, since your code modifies the original inputs.

  • 0

    This is a pretty sexy solution.

  • 0

    Good! I also think we should not modify the passed in array.

  • 0

    very nice idea! Thanks for the share...

  • 0
    This post is deleted!

  • 0

    Fantastic solution. These dp problems are actually logic problems according to my opinion.

  • 0

    I didn't understand the problem, can someone please help?


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.