LeetCode刷题【265】粉刷房子 II

假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 
     或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5. 

进阶：
您能否在 O(nk) 的时间复杂度下解决此问题？

参见LeetCode刷题【256】粉刷房子，和LeetCode刷题【剑指 Offer II 091】粉刷房子依旧是动态规划

class Solution {
    public int minCostII(int[][] costs) {
        int[][] dp = new int[costs.length][costs[0].length];
        for (int i = 0; i < costs[0].length; i++) {
            dp[0][i] = costs[0][i];
        }
        int i = 1;
        for (; i < costs.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = minExceptIndex(dp[i-1],j) + costs[i][j];
            }
        }
        return minExceptIndex(dp[--i],-1 );
    }

    public int minExceptIndex(int[] arr, int index){
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (i==index){
                continue;
            }
            min = Math.min(min,arr[i]);
        }
        return min;
    }
}

然后接下来看一下minExceptIndex这个方法，想要在O（nk）的时间复杂度的话，我们知道minExceptIndex实际是遍历某一行dp值，找出这行中除了指定的某个索引之后的最小值，而这个最小值的话肯定只有唯一一个，所以我们可以在遍历的时候记录几个信息

1. 当前dp行内的最小值
2. 最小值对应的索引值，可能有多个
3. 除了最小值之外的最小值，也就是第二最小的值

把这几个信息记录下来的话，当dp[i]的时候，只需遍历一次即可了即实现O（nk）的时间复杂度