leetcode265 -- Paint House II (hard)

leetcode265 -- Paint House II (hard)

题目

现在题目变了,变成了

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2]is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

意思是这里给了一个花费矩阵costs.然后要根据这个矩阵来算出最小的花费。

其实如果不考虑时间复杂度的话,并不是特别难,比如


如果说f(i, j)是在第i个房间涂第j种颜色的最优解,那么方程式就是

f(i, j) = costs(i, j) + min(f(i - 1, x)) 其中x 是(0, 1, 2, 3, ... k)中除去 j的集合(因为不能相邻房间不能同色)

上面的最优解的意思是假设就总共(i+1)个房子的时候,那么上面的i就是最后一个房子了。这个不难理解,但是这样的复杂度是O(nk^2).如何把求最小值的那个优化到O(1)是关键,具体的可以参考blog,其实还是拿空间换时间。

参考

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦