Leetcode-265 粉刷房子2 题解

题目详情

假如有一排房子，共 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) 的时间复杂度下解决此问题

题目分析

该题是在粉刷房子1的基础上进行的扩展，将颜色的数量扩展到了k，同时加上了一个nk的时间复杂度的限制。

主要的解题分为两部分。

第一部分主要是实现nk2的时间复杂度求解。
这个就是一个dp问题，从第一个房子开始，记录下该房子的每种颜色下的最小消耗。
然后进行迭代，后一个房子要根据前一个房子的颜色，来判断自己粉刷颜色c时，最小消耗。
状态转移方程是：
f [ i ] [ j ] = m i n t ! = j { f [ i − 1 ] [ 0 ] , . . . f [ i − 1 ] [ t ] . . } + c o s t s [ i − 1 ] [ j ] f[i][j] = min_{t!=j}\{f[i-1][0],...f[i-1][t].. \}+costs[i-1][j] f[i][j]=mint!=j​{f[i−1][0],...f[i−1][t]..}+costs[i−1][j]
其中可变变量有两个，最小消耗，颜色
如此便可解决nk2的问题

第二部分是从nk2降到nk
这里主要优化点在于k2
按照第一部分的逻辑，当前房子的每种颜色的最小消耗需要去遍历前一个房子的k个颜色的消耗，找到不包括当前房子颜色的最小值。O(k)
因为有k种颜色，所以就是O(k2)。

针对这个问题，就变成了，输入k个数的数组，返回一个数组，数组的每个位置值为：除去当前值的最小值。就变成了这样一个问题。

针对该问题，我们可以这样来进行解决。对于k个数，我们可以确定的一点是，对于最小值的数，它的位置应该填除去最小值的次小值。
而对于其他位置，应该填的都是最小值。

那么问题就清晰了，我们只要找到k个数中的最小值，次小值，以及其对应的坐标，那么这个问题就能在O(k)内解决了。

所以该题实际是两个小题目的一个组合。

实现代码

class Solution {
    //先写一个nk2的
    //可能会出现只有一种颜色，那么这种特殊情况，肯定只有一个房子
    //然后如何从k2到k
    //有k个值，求除了i之外的最小值(i∈[1,k])
    //如果最小值是第i个元素，次小值是第j个元素
    //那么除了i之外的最小值是第j个元素
    //而除了其他的元素，最小值都是第i个元素
    //有趣，这时降为nk
    public int minCostII(int[][] costs) {
        if(costs==null || costs.length==0)return 0;
        if(costs[0].length==1) return costs[0][0];
        //创建dp数组并进行初始化
        int m = costs.length;
        int n = costs[0].length;
        int[][] dp = new int[m+1][n];
        //进行计算
        for(int i=1; i<=m; i++){//对于第i个房子
            int minValue = Integer.MAX_VALUE;
            int secMinValue = Integer.MAX_VALUE;
            int minIndex =-1;
            int secMinIndex = -1;
            for(int j=0; j<n; j++){//对于第j种颜色
                if(dp[i-1][j]<minValue){
                    secMinValue = minValue;
                    minValue = dp[i-1][j];
                    secMinIndex = minIndex;
                    minIndex = j;
                }
                else if(dp[i-1][j]<secMinValue){
                    secMinValue = dp[i-1][j];
                    secMinIndex = j;
                }
            }
            for(int j=0; j<n; j++){
                dp[i][j] = (j==minIndex?secMinValue:minValue) +costs[i-1][j];
            }
        }
        //返回最小值
        int res = Integer.MAX_VALUE;
        for(int k=0; k<n; k++){
            res = Math.min(res,dp[costs.length][k]);
        }
        return res;

    }
}