Lintcode516 Paint House II solut
【题目描述】
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.
Notice
All costs are positive integers.
这里有n个房子在一列直线上，现在我们需要给房屋染色，共有k种颜色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。
费用通过一个nxk 的矩阵给出，比如cost[0][0]表示房屋0染颜色0的费用，cost[1][2]表示房屋1染颜色2的费用。
注意事项
所有费用都是正整数
【题目链接】
www.lintcode.com/en/problem/paint-house-ii/
【题目解析】
只记录3个值，即前一行最小值，第二小值，和最小值的index。
更新当前行元素，当前行元素记录的是当前行房子涂该种颜色时的最小值，只可能由该元素与上一行的最小值或次小值加和得到。遍历当前行的每个元素，若该元素的列和前一行最小值index不同，则更新为当前行元素值＋上一行最小值，若和上一行最小值index相同，则更新为当前元素值＋上一行次小值。同时将该值和当前行的最小值和次小值比较，更新当前行的最小值，次小值和最小值的index。
重复2直到遍历所有行。
【参考答案】
