What is the main dynamic programming pattern in Paint House III?

The problem uses state transition DP, where each state tracks the current house index, number of neighborhoods formed, and last painted color to determine minimal costs.

How do I handle houses that are already painted?

Skip cost addition for painted houses and enforce their color in the DP state transitions, ensuring neighborhoods are counted correctly.

What if it's impossible to form the exact target neighborhoods?

If no DP state reaches the target number of neighborhoods, return -1 as required by the problem statement.

Can the DP approach handle the maximum constraints efficiently?

Yes, by iterating over m, n, and target states with proper pruning and memoization, the solution remains feasible for m <= 100 and n <= 20.

Why is state transition DP necessary for Paint House III?

Because each house's paint choice affects neighborhood formation and total cost, DP efficiently tracks all feasible sequences to guarantee exact target neighborhoods.

#1473

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

粉刷房子 III

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区…

数组动态规划

题目描述

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。

示例 1：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。

示例 3：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5

示例 4：

输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

提示：

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j][k]$ 表示将下标 $[0,..i]$ 的房子涂上颜色，最后一个房子的颜色为 $j$ ，且恰好形成 $k$ 个街区的最小花费。那么答案就是 $f[m-1][j][\textit{target}]$ ，其中 $j$ 的取值范围为 $[1,..n]$ 。初始时，我们判断下标为 $0$ 的房子是否已经涂色，如果未涂色，那么 $f[0][j][1] = \textit{cost}[0][j - 1]$ ，其中 $j \in [1,..n]$ 。如果已经涂色，那么 $f[0][\textit{houses}[0]][1] = 0$ 。其他的 $f[i][j][k]$ 的值都初始化为 $\infty$ 。

接下来，我们从下标 $i=1$ 开始遍历，对于每个 $i$ ，我们判断下标为 $i$ 的房子是否已经涂色：

如果未涂色，那么我们可以将下标为 $i$ 的房子涂成颜色 $j$ ，我们枚举街区的数量 $k$ ，其中 $k \in [1,..\min(\textit{target}, i + 1)]$ ，并且枚举下标为 $i$ 的房子的前一个房子的颜色 $j_0$ ，其中 $j_0 \in [1,..n]$ ，那么我们可以得到状态转移方程：

f[i][j][k] = \min_{j_0 \in [1,..n]} \{ f[i - 1][j_0][k - (j \neq j_0)] + \textit{cost}[i][j - 1] \}

如果已经涂色，那么我们可以将下标为 $i$ 的房子涂成颜色 $j$ ，我们枚举街区的数量 $k$ ，其中 $k \in [1,..\min(\textit{target}, i + 1)]$ ，并且枚举下标为 $i$ 的房子的前一个房子的颜色 $j_0$ ，其中 $j_0 \in [1,..n]$ ，那么我们可以得到状态转移方程：

f[i][j][k] = \min_{j_0 \in [1,..n]} \{ f[i - 1][j_0][k - (j \neq j_0)] \}

最后，我们返回 $f[m - 1][j][\textit{target}]$ ，其中 $j \in [1,..n]$ ，如果所有的 $f[m - 1][j][\textit{target}]$ 的值都为 $\infty$ ，那么返回 $-1$ 。

时间复杂度 $O(m \times n^2 \times \textit{target})$ ，空间复杂度 $O(m \times n \times \textit{target})$ 。其中 $m$ , $n$ , $\textit{target}$ 分别为房子的数量，颜色的数量，街区的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

class Solution:
    def minCost(
        self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
    ) -> int:
        f = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
        if houses[0] == 0:
            for j, c in enumerate(cost[0], 1):
                f[0][j][1] = c
        else:
            f[0][houses[0]][1] = 0
        for i in range(1, m):
            if houses[i] == 0:
                for j in range(1, n + 1):
                    for k in range(1, min(target + 1, i + 2)):
                        for j0 in range(1, n + 1):
                            if j == j0:
                                f[i][j][k] = min(
                                    f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]
                                )
                            else:
                                f[i][j][k] = min(
                                    f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]
                                )
            else:
                j = houses[i]
                for k in range(1, min(target + 1, i + 2)):
                    for j0 in range(1, n + 1):
                        if j == j0:
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j][k])
                        else:
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1])

        ans = min(f[-1][j][target] for j in range(1, n + 1))
        return -1 if ans >= inf else ans

speed

复杂度分析

指标	值
时间	and space complexity depend on m, n, and target. Standard DP leads to O(m * n * target * n) time and O(m * target * n) space, reflecting iteration over houses, colors, and neighborhood states.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Consider edge cases where houses are already painted and may limit valid neighborhood formation.
question_mark
Check for impossibility early if initial painted houses exceed target neighborhoods.
question_mark
Optimize state transitions to avoid redundant recalculations for all color combinations.

warning

常见陷阱

外企场景

error
Ignoring already painted houses and adding paint costs incorrectly.
error
Incorrectly incrementing neighborhood count when consecutive houses have the same color.
error
Overlooking cases where forming exactly target neighborhoods is impossible, returning wrong cost.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the neighborhood definition to allow non-consecutive same-colored houses and track differently in DP.
arrow_right_alt
Introduce additional constraints like limiting specific colors for certain houses.
arrow_right_alt
Optimize for large n by pruning DP states using memoization of only feasible previous color transitions.

help

常见问题

外企场景

继续练习

#1477 找两个和为目标值且不重叠的子数组 #1478 安排邮筒 #1467 两个盒子中球的颜色数相同的概率