http://www.lintcode.com/en/problem/paint-house-ii/#
刷房子，每个房子刷每种颜色有一个cost[i][j]，相邻两个房子不能刷同一种颜色，求最小cost
要求时间复杂度O(NK)
每次不需要前一状态的所有值，只需要保存前一状态之中最小和第二小的所涂的颜色。
内层循环初始值设置为-1
public class Solution { /** * @param costs n x k cost matrix * @return an integer, the minimum cost to paint all houses */ public int minCostII(int[][] costs) { // Write your code here if (costs == null || costs.length == 0) { return 0; } int min1 = -1; int min2 = -1; int[][] cache = costs.clone(); for (int i = 0; i < costs.length; i++) { int last1 = min1; int last2 = min2; min1 = -1; min2 = -1; for (int j = 0; j < costs[0].length; j++) { if (j != last1) { cache[i][j] += last1 < 0 ? 0 : cache[i - 1][last1]; } else { cache[i][j] += last2 < 0 ? 0 : cache[i - 1][last2]; } if (min1 < 0 || cache[i][min1] > cache[i][j]) { min2 = min1; min1 = j; } else if (min2 < 0 || cache[i][min2] > cache[i][j]) { min2 = j; } } } return cache[costs.length - 1][min1]; } }