Simple java DP solution


  • 95
    Y

    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) {
        if(costs==null||costs.length==0){
            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]);
    }
    

    }


  • 66

    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 {
    public:
        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
    V

    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

    jianchao.li.fighter's answer seems better, since your code modifies the original inputs.


  • 0
    C

    This is a pretty sexy solution.


  • 0
    A

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


  • 0
    N

    very nice idea! Thanks for the share...


  • 0
    F
    This post is deleted!

  • 0
    V

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


  • 0
    D

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

    Thanks,
    D


Log in to reply
 

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