【Leetcode】265. Paint House II

题目地址：

https://leetcode.com/problems/paint-house-ii/

给定一个 n × k n\times k n×k的数组 A A A， A [ i ] [ j ] A[i][j] A[i][j]表示第 i i i个房子涂第 j j j种颜色的油漆所需要的花费（都是从 0 0 0开始计数的）。一共 n n n个房子， k k k种油漆颜色，并且下标连续的两个房子不能涂相同的颜色。要将这些房子都涂上颜色，问最小花费是多少。

思路是动态规划。涂色方案可以按照最后一个房子涂哪种颜色来分类。设 f [ i ] [ j ] f[i][j] f[i][j]表示在第 i i i个房子涂第 j j j种颜色的情况下的 0 ∼ i 0\sim i 0∼i的房子的最小花费，那么就有： f [ i ] [ j ] = min ⁡ j ′ ≠ j { f [ i − 1 ] [ j ′ ] } + c [ i ] [ j ] f[i][j]=\min_{j'\ne j}\{f[i-1][j']\}+c[i][j] f[i][j]=j′​=jmin​{f[i−1][j′]}+c[i][j]我们可以发现，计算 f [ i ] [ j ] f[i][j] f[i][j]的时候需要知道数组 f [ i − 1 ] f[i-1] f[i−1]里的最小值。进一步发现，如果 j j j恰好使得 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]最小，那么计算 f [ i ] [ j ] f[i][j] f[i][j]的时候还需要数组 f [ i − 1 ] f[i-1] f[i−1]里的次小值。所以在计算 f [ i ] [ j ] f[i][j] f[i][j]的时候，我们需要预处理一遍数组 f [ i − 1 ] f[i-1] f[i−1]里的最小值、最小值出现的下标和次小值。这样就能将时间复杂度降低到 O ( n k ) O(nk) O(nk)。至于空间复杂度的优化，可以采用滚动数组的方式降低到 O ( k ) O(k) O(k)。代码如下：

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        // n为房子数量, m为颜色数量
        int n = costs.length, m = costs[0].length;
        int[][] dp = new int[2][m];
        // 初始化为第0个房子涂各个颜色的花费
        for (int i = 0; i < m; i++) {
            dp[0][i] = costs[0][i];
        }
        
        // 滚动数组下标
        int curIdx = 1;
        for (int i = 1; i < n; i++) {
        	// 滚动到下一个位置
        	curIdx ^= 1;
        	// 预处理一下dp[curIdx]的最小值、最小值出现的下标和次小值
            int minCost1 = Integer.MAX_VALUE, minIdx1 = 0;
            int minCost2 = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                if (dp[curIdx][j] < minCost1) {
                    minCost2 = minCost1;
                    minCost1 = dp[curIdx][j];
                    minIdx1 = j;
                } else if (dp[curIdx][j] < minCost2) {
                    minCost2 = dp[curIdx][j];
                }
            }
            
            // 开始更新dp[curIdx ^ 1]，也就是前i个房子的花费
            for (int j = 0; j < m; j++) {
                if (j == minIdx1) {
                    dp[curIdx ^ 1][j] = minCost2 + costs[i][j];
                } else {
                    dp[curIdx ^ 1][j] = minCost1 + costs[i][j];
                }
            }
        }
        
        // 答案就是最后一个房子涂各个颜色的总花费的最小值
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            res = Math.min(res, dp[curIdx ^ 1][i]);
        }
        
        return res;
    }
}
           

时间复杂度 O ( n k ) O(nk) O(nk)，空间 O ( k ) O(k) O(k)。