原题链接在这里：https://leetcode.com/problems/paint-house-ii/
题目：
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.
题解：
类似Paint House. k中不同的颜色. paint当前house时, 若是当前的颜色k与之前最小cost的颜色不同时，加上之前的最小值. 若是当前k与之前相同就选之前给出第二小cost的颜色.
Time Complexity: O(kn). Space: O(1).
AC Java:
1 public class Solution { 2 public int minCostII(int[][] costs) { 3 if(costs == null || costs.length == 0){ 4 return 0; 5 } 6 int min1 = 0; //当前这个house涂完最小的cost 7 int min2 = 0; //当前这个house涂完第二小的cost 8 int lastColor = -1; //上个house选择的颜色 9 for(int i = 0; i<costs.length; i++){ 10 int curMin1 = Integer.MAX_VALUE; //选择到当前颜色时的最小cost 11 int curMin2 = Integer.MAX_VALUE; //选择到当前颜色时的第二小cost 12 int curColor = -1; 13 for(int k = 0; k<costs[i].length; k++){ 14 int newCost = costs[i][k] + (k == lastColor ? min2 : min1); 15 if(newCost < curMin1){ 16 curMin2 = curMin1; 17 curMin1 = newCost; 18 curColor = k; 19 }else if(newCost < curMin2){ 20 curMin2 = newCost; 21 } 22 } 23 min1 = curMin1; 24 min2 = curMin2; 25 lastColor = curColor; 26 } 27 return min1; 28 } 29 }
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/5327633.html