Lintcode515 Paint House solution

【题目描述】

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[i][j]表示第i幢房子涂j的颜色最小的总和，即从前一幢房子的状态dp[i-1][] (k != j)中选一个最小的再加上给第i幢房子涂j颜色的cost。如果直接在costs上修改，则不用单独开dp的空间，可以优化空间。

【参考答案】

www.jiuzhang.com/solutions/paint-house/