Simple java DP solution

• 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]);
}
``````

}

• 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)`.

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

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

• This is a pretty sexy solution.

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

• very nice idea! Thanks for the share...

• This post is deleted!

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

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

Thanks,
D

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