|
|
【题目描述】
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
Notice
All costs are positive integers.
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。
费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用。
注意事项
所有费用都是正整数
【题目链接】
www.lintcode.com/en/problem/paint-house/
【题目解析】
这道题只有3种颜色，所以很简单。dp[j]表示第i幢房子涂j的颜色最小的总和，即从前一幢房子的状态dp[i-1][] (k != j)中选一个最小的再加上给第i幢房子涂j颜色的cost。如果直接在costs上修改，则不用单独开dp的空间，可以优化空间。
【参考答案】
www.jiuzhang.com/soluti**/paint-house/
|
|
