LeetCode 265. 粉刷房子 II

Categories:

题目描述
思路分析
1. 解法一：DP + 最小二值（推荐）
相似题目

题目描述

✅ 265. 粉刷房子 II

思路分析

解法一：DP + 最小二值（推荐）

核心思路：

对每一行维护上一行的最小值与次小值。

当前颜色若不是最小值颜色，用最小值转移；否则用次小值。

使整体时间从 O(nk^2) 降到 O(nk)。

复杂度分析：

时间复杂度：O(nk)，其中 n 表示房子数，k 表示颜色数。

空间复杂度：O(k)。

class Solution {
    public int minCostII(int[][] costs) {
        if (costs.length == 0) {
            return 0;
        }

        int k = costs[0].length;
        int[] dp = new int[k];

        for (int i = 0; i < costs.length; i++) {
            int min1 = -1;
            int min2 = -1;

            for (int j = 0; j < k; j++) {
                if (min1 == -1 || dp[j] < dp[min1]) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || dp[j] < dp[min2]) {
                    min2 = j;
                }
            }

            int[] ndp = new int[k];
            for (int j = 0; j < k; j++) {
                int best = (j == min1 ? dp[min2] : dp[min1]);
                if (min2 == -1) {
                    best = dp[min1];
                }
                ndp[j] = costs[i][j] + best;
            }

            dp = ndp;
        }

        int ans = Integer.MAX_VALUE;
        for (int v : dp) {
            ans = Math.min(ans, v);
        }
        return ans;
    }
}

func minCostII(costs [][]int) int {
	if len(costs) == 0 {
		return 0
	}

	k := len(costs[0])
	dp := make([]int, k)

	for i := 0; i < len(costs); i++ {
		min1, min2 := -1, -1
		for j := 0; j < k; j++ {
			if min1 == -1 || dp[j] < dp[min1] {
				min2 = min1
				min1 = j
			} else if min2 == -1 || dp[j] < dp[min2] {
				min2 = j
			}
		}

		ndp := make([]int, k)
		for j := 0; j < k; j++ {
			best := dp[min1]
			if j == min1 && min2 != -1 {
				best = dp[min2]
			}
			ndp[j] = costs[i][j] + best
		}
		dp = ndp
	}

	ans := dp[0]
	for _, v := range dp {
		if v < ans {
			ans = v
		}
	}
	return ans
}

相似题目

题目	难度	考察点
265. 粉刷房子 II	困难	DP
256. 粉刷房子	中等	DP
276. 栅栏涂色	中等	DP
1411. 给 N x 3 网格图涂色的方案数	困难	DP
516. 最长回文子序列	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/83373424