Leetcode 265: Paint house II

July 2, 2018

Introduction

It is a hard level algorithm called Paint house II. And I like to use this blog to read problem statement.

30 minutes study

Now it is 11:09 AM, I like to spend 30 minutes on the algorithm.

One of ideas is to solve the problem using dynamic programming. At each position of houses, index, it is to get minimum cost to paint each color with color Id.

I notice that greedy algorithm will not work. If every house index the minimum cost is saved without color Id, next time the minimum can not be generated by previous minimum cost. Since we have to compare all colors, the previous one's color id is unknown.

To solve the problem, we have to keep the minimum cost for each index with each color. That is a lot of calculation. Each color ...

I need to get hints to think about simplifying the problem, only keep last two minimum values. Therefore, all colors can be considered for each index position. This is a major hint I need in my thinking process.

Solution study

Here is Chinese version of discussion from the blog:

题解：

是Paint House I的generalized版本。这回颜色不是RGB三种，而是扩展到了K种。正好可以试试在Paint House I中没用上的想法。思路还是使用DP, 这回我们需要维护一个刷当前房子之前所有房子最小的花费min1，以及倒数第二小的花费min2。然后我们再遍历当前房子i所有color的花费，假如这个颜色与之前i-1号房子的颜色相同，我们选择min2，否则选择min1。比较完所有颜色以后我们记录下来当前的curMin1，curMin2以及current color， 更新min1，min2和lastColor，就可以继续计算下一个房子了。

Time Complexity - O(n)， Space Complexity - O(1)