LeetCode 1473. 粉刷房子 III

Categories:

题目描述
思路分析
1. 解法一：三维 DP（推荐）
相似题目

题目描述

✅ 1473. 粉刷房子 III

思路分析

解法一：三维 DP（推荐）

核心思路：

dp[i][j][k] 表示前 i 个房子，最后颜色为 j，形成 k 个街区的最小成本。

若第 i 个房子已涂色，只能选该色；否则尝试全部颜色。

转移时根据颜色是否变化更新街区数。

复杂度分析：

时间复杂度：O(m _ n^2 _ target)。

空间复杂度：O(m _ n _ target)。

class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int INF = 1_000_000_000;
        int[][][] dp = new int[m + 1][n + 1][target + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= target; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }

        dp[0][0][0] = 0;
        for (int i = 1; i <= m; i++) {
            int color = houses[i - 1];
            for (int j = 1; j <= n; j++) {
                if (color != 0 && color != j) {
                    continue;
                }
                int paintCost = (color == 0) ? cost[i - 1][j - 1] : 0;
                for (int pj = 0; pj <= n; pj++) {
                    for (int k = 0; k <= target; k++) {
                        if (dp[i - 1][pj][k] == INF) {
                            continue;
                        }
                        int nk = k + (pj == j ? 0 : 1);
                        if (nk > target) {
                            continue;
                        }
                        dp[i][j][nk] = Math.min(dp[i][j][nk], dp[i - 1][pj][k] + paintCost);
                    }
                }
            }
        }

        int ans = INF;
        for (int j = 1; j <= n; j++) {
            ans = Math.min(ans, dp[m][j][target]);
        }
        return ans == INF ? -1 : ans;
    }
}

func minCost(houses []int, cost [][]int, m int, n int, target int) int {
    const inf = 1_000_000_000
    dp := make([][][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([][]int, n+1)
        for j := 0; j <= n; j++ {
            dp[i][j] = make([]int, target+1)
            for k := 0; k <= target; k++ {
                dp[i][j][k] = inf
            }
        }
    }

    dp[0][0][0] = 0
    for i := 1; i <= m; i++ {
        color := houses[i-1]
        for j := 1; j <= n; j++ {
            if color != 0 && color != j {
                continue
            }
            paintCost := 0
            if color == 0 {
                paintCost = cost[i-1][j-1]
            }
            for pj := 0; pj <= n; pj++ {
                for k := 0; k <= target; k++ {
                    if dp[i-1][pj][k] == inf {
                        continue
                    }
                    nk := k
                    if pj != j {
                        nk++
                    }
                    if nk > target {
                        continue
                    }
                    val := dp[i-1][pj][k] + paintCost
                    if val < dp[i][j][nk] {
                        dp[i][j][nk] = val
                    }
                }
            }
        }
    }

    ans := inf
    for j := 1; j <= n; j++ {
        if dp[m][j][target] < ans {
            ans = dp[m][j][target]
        }
    }
    if ans == inf {
        return -1
    }
    return ans
}

相似题目

题目	难度	考察点
1420. 生成数组	困难	DP
1335. 工作计划的最低难度	困难	DP
309. 最佳买卖股票时机含冷冻期	中等	DP
312. 戳气球	困难	DP
64. 最小路径和	中等	DP

本文作者: HGNULB

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