最多相邻k个房屋可粉刷同一颜色的粉刷房子 III（Paint House III）进阶问题
字数 3561 2025-12-07 11:02:49

最多相邻k个房屋可粉刷同一颜色的粉刷房子 III（Paint House III）进阶问题

题目描述

假设有m栋房子排成一排，每栋房子可以粉刷n种颜色之一（颜色编号1到n），但要求某些房子已经预先粉刷了特定颜色（不能更改），而未粉刷的房子需要你决定颜色。粉刷完所有房子后，会形成若干个“街区”（street）：连续相同颜色的房子属于同一个街区。比如，房子颜色为[1,2,2,1,1,2]，则形成4个街区。

现在给定一个目标街区数target，以及一个整数k。你的目标是：在满足“任何颜色在整排房子中最多只能有k栋相邻的房子被粉刷成该颜色”的前提下，通过选择未粉刷房子的颜色，使得最终形成的街区总数恰好等于target。每栋房子粉刷成不同颜色有不同的成本（成本矩阵costs，其中costs[i][j]表示将房子i粉刷成颜色j的成本，如果房子i已预刷颜色j，则costs[i][j]=0，且不允许粉刷成其他颜色）。

你需要计算出满足上述所有条件的最小总粉刷成本。如果无法达成，返回-1。

问题形式化

  • 输入：m（房子数量，编号0到m-1），n（颜色数量，编号1到n），target（目标街区数），k（任何颜色最多允许相邻的房屋数），数组houses（长度m，houses[i]=0表示未粉刷，1~n表示已粉刷的颜色），成本矩阵costs（m x n）。
  • 输出：最小总成本，或-1。

示例
m=4, n=3, target=3, k=2
houses=[0,0,0,1]（最后一栋已刷颜色1）
costs=[[1,2,3],[4,5,6],[7,8,9],[0,0,0]]
解释：前3栋未刷，最后1栋已刷颜色1（成本0）。最多相邻2栋同色。需要最终街区数=3。
一种方案：颜色[2,2,1,1]，街区：颜色2（连续2栋），颜色1（连续2栋），但街区数=2≠3。不行。
另一种：[2,3,1,1]，街区：2,3,1，街区数=3，检查相邻限制：颜色1相邻2栋（房子2和3）未超k=2，颜色2和3都只1栋，满足。成本=cost[0][2]+cost[1][3]+cost[2][1]=3+6+7=16。需寻找最小成本。

解题思路

这个问题是经典“粉刷房子 III”（LeetCode 1473）的进阶版，增加了“相邻同色房屋数不超过k”的限制。这使得状态设计需要额外记录当前颜色已连续出现了多少栋。

  1. 状态定义

    • 设dp[i][j][t][c]表示：考虑前i栋房子（0~i-1），第i-1栋房子粉刷成颜色j，且到这栋为止，颜色j已经连续出现了c栋（c从1到k），并且前i栋房子形成了t个街区，所需的最小成本。
    • 注意：i的范围0~m，j的范围1~n，t的范围0~target，c的范围1~k。
    • 初始时，i=0（没有房子），状态不好表示，我们通常从i=1开始递推，初始化i=1的情况。

  2. 状态转移

    • 当处理到第i栋房子（原始下标i-1）时，我们需要考虑它的颜色选择：
      a) 如果该房子已预刷颜色p（houses[i-1]=p≠0），那么我们只能尝试j=p的情况。
      b) 如果未刷（houses[i-1]=0），则可以尝试所有颜色j=1~n。
    • 对于固定的目标颜色j，我们需要从前一栋房子的颜色j'和连续计数c'转移过来：
      • 如果j' == j，则颜色连续，新区块数不变（t不变），连续计数c=c'+1，但必须满足c≤k。
      • 如果j' ≠ j，则颜色改变，新区块数t'=t-1（因为当前房子开启新区块），连续计数c重置为1。
    • 因此转移方程为（记当前房子成本为cost = (houses[i-1]==0? costs[i-1][j-1] : 0)，若houses[i-1]固定且不为j，则该j不可选）：
      dp[i][j][t][c] = min {
      // 从同色j转移
      if c>1: dp[i-1][j][t][c-1] + cost,
      // 从不同色j'转移
      for j'≠j: dp[i-1][j'][t-1][c'] + cost, 其中c'是任意1~k
      }
    • 注意：t的范围是1~target，c的范围是1~k。当t=0时，只有i=0或所有房子同色且c=i的情况，但我们的t是街区数，不可能为0除非没房子，我们最终要求t=target。

  3. 初始化

    • 第一栋房子（i=1）：
      • 如果已刷颜色p：则dp[1][p][1][1] = 0（因为第一栋成本为0，且形成一个街区，连续计数1）。
      • 如果未刷：对每种颜色j，dp[1][j][1][1] = costs[0][j-1]。
    • 其他状态初始化为无穷大（表示不可达）。

  4. 最终答案

    • 遍历最后一栋房子的颜色j和连续计数c=1~k，取dp[m][j][target][c]的最小值。
    • 如果所有都是无穷大，返回-1。

  5. 复杂度优化

    • 直接四维dp空间O(m * n * target * k)可能较大，但k通常不大。
    • 可以滚动数组优化第一维（房子），空间O(n * target * k)。
    • 注意：在计算不同色转移时，需要快速找到dp[i-1][j'][t-1][c']的最小值（对所有j'≠j，c'任意）。可以预处理：对于每个t，维护两个最小值：全局最小值min1（及其颜色j1），和全局次小值min2（颜色j2≠j1）。这样对于当前颜色j，如果j==j1，则用min2，否则用min1。因为我们需要j'≠j的最小值。同时，由于c'维度，我们需要的是所有c'中最小的dp[i-1][j'][t-1][c']，所以我们可以在计算dp[i-1]时，对每个(j,t)维护best[j][t] = min_{c'} dp[i-1][j][t][c']，然后用上述min1/min2技巧快速得到不同色转移的最小值。

逐步计算示例（简化版，便于理解）

假设m=2,n=2,target=2,k=1（即不允许相邻同色！）。
houses=[0,0]，costs=[[1,2],[3,4]]。

初始化i=1：
dp[1][1][1][1]=cost[0][0]=1
dp[1][2][1][1]=cost[0][1]=2

i=2（第二栋房子）：
对颜色j=1（cost=3）：

  • 同色转移：需要c>1，但k=1，不允许c=2，所以不考虑。
  • 不同色转移：从前一栋颜色j'=2，t-1=1，c'任意（这里只有1）：
    dp[1][2][1][1]=2，所以dp[2][1][2][1]=2+3=5。
    对颜色j=2（cost=4）：
  • 不同色转移：从前一栋颜色j'=1，t-1=1：
    dp[1][1][1][1]=1，所以dp[2][2][2][1]=1+4=5。

最终，target=2，取min(dp[2][1][2][1], dp[2][2][2][1])=5。

验证：两栋房子必须不同色才能有2个街区，且相邻不同色满足k=1。最小成本是颜色1然后颜色2：成本1+4=5，或颜色2然后颜色1：成本2+3=5。正确。

实现细节

  1. 初始化dp为INF，然后初始化i=1。
  2. 从i=2到m循环：
    • 先计算best[j][t] = min_{c} dp_prev[j][t][c]。
    • 对每个t，用best数组计算全局最小min1和次小min2。
    • 对当前房子尝试每种颜色j（如果已预刷则只尝试该颜色）：
      • 计算cost_j。
      • 对t从1到target，c从1到k：
        a) 同色转移：如果c>1，从dp_prev[j][t][c-1]转移。
        b) 不同色转移：如果t>1，从min_{j'≠j} best[j'][t-1]转移（利用min1/min2快速得到）。
        取a和b的最小值，加上cost_j，更新dp_cur[j][t][c]。
  3. 最终答案：min_{j,c} dp[m][j][target][c]，若为INF则-1。

时间复杂度：O(m * n * target * k)，但通过min1/min2优化，不同色转移可O(1)完成，所以实际上是O(m * n * target * k)但常数较小。

小结：这道题是粉刷房子III的强化版，增加了相邻同色数的限制。关键是在状态中增加连续计数c，并在转移时处理连续与不连续两种情况。利用前缀最小值的技巧优化不同色转移的枚举，从而在合理时间内求解。

最多相邻k个房屋可粉刷同一颜色的粉刷房子 III（Paint House III）进阶问题 题目描述 假设有m栋房子排成一排，每栋房子可以粉刷n种颜色之一（颜色编号1到n），但要求某些房子已经预先粉刷了特定颜色（不能更改），而未粉刷的房子需要你决定颜色。粉刷完所有房子后，会形成若干个“街区”（street）：连续相同颜色的房子属于同一个街区。比如，房子颜色为[ 1,2,2,1,1,2 ]，则形成4个街区。 现在给定一个目标街区数target，以及一个整数k。你的目标是：在满足“任何颜色在整排房子中最多只能有k栋相邻的房子被粉刷成该颜色”的前提下，通过选择未粉刷房子的颜色，使得最终形成的街区总数恰好等于target。每栋房子粉刷成不同颜色有不同的成本（成本矩阵costs，其中costs[ i][ j]表示将房子i粉刷成颜色j的成本，如果房子i已预刷颜色j，则costs[ i][ j ]=0，且不允许粉刷成其他颜色）。 你需要计算出满足上述所有条件的最小总粉刷成本。如果无法达成，返回-1。 问题形式化 输入：m（房子数量，编号0到m-1），n（颜色数量，编号1到n），target（目标街区数），k（任何颜色最多允许相邻的房屋数），数组houses（长度m，houses[ i ]=0表示未粉刷，1~n表示已粉刷的颜色），成本矩阵costs（m x n）。 输出：最小总成本，或-1。 示例 m=4, n=3, target=3, k=2 houses=[ 0,0,0,1 ]（最后一栋已刷颜色1） costs=[ [ 1,2,3],[ 4,5,6],[ 7,8,9],[ 0,0,0] ] 解释：前3栋未刷，最后1栋已刷颜色1（成本0）。最多相邻2栋同色。需要最终街区数=3。 一种方案：颜色[ 2,2,1,1 ]，街区：颜色2（连续2栋），颜色1（连续2栋），但街区数=2≠3。不行。 另一种：[ 2,3,1,1]，街区：2,3,1，街区数=3，检查相邻限制：颜色1相邻2栋（房子2和3）未超k=2，颜色2和3都只1栋，满足。成本=cost[ 0][ 2]+cost[ 1][ 3]+cost[ 2][ 1 ]=3+6+7=16。需寻找最小成本。 解题思路 这个问题是经典“粉刷房子 III”（LeetCode 1473）的进阶版，增加了“相邻同色房屋数不超过k”的限制。这使得状态设计需要额外记录当前颜色已连续出现了多少栋。 状态定义 设dp[ i][ j][ t][ c ]表示：考虑前i栋房子（0~i-1），第i-1栋房子粉刷成颜色j，且到这栋为止，颜色j已经连续出现了c栋（c从1到k），并且前i栋房子形成了t个街区，所需的最小成本。 注意：i的范围0~m，j的范围1~n，t的范围0~target，c的范围1~k。 初始时，i=0（没有房子），状态不好表示，我们通常从i=1开始递推，初始化i=1的情况。 状态转移 当处理到第i栋房子（原始下标i-1）时，我们需要考虑它的颜色选择： a) 如果该房子已预刷颜色p（houses[ i-1 ]=p≠0），那么我们只能尝试j=p的情况。 b) 如果未刷（houses[ i-1 ]=0），则可以尝试所有颜色j=1~n。 对于固定的目标颜色j，我们需要从前一栋房子的颜色j'和连续计数c'转移过来： 如果j' == j，则颜色连续，新区块数不变（t不变），连续计数c=c'+1，但必须满足c≤k。 如果j' ≠ j，则颜色改变，新区块数t'=t-1（因为当前房子开启新区块），连续计数c重置为1。 因此转移方程为（记当前房子成本为cost = (houses[ i-1]==0? costs[ i-1][ j-1] : 0)，若houses[ i-1 ]固定且不为j，则该j不可选）： dp[ i][ j][ t][ c ] = min { // 从同色j转移 if c>1: dp[ i-1][ j][ t][ c-1 ] + cost, // 从不同色j'转移 for j'≠j: dp[ i-1][ j'][ t-1][ c' ] + cost, 其中c'是任意1~k } 注意：t的范围是1~target，c的范围是1~k。当t=0时，只有i=0或所有房子同色且c=i的情况，但我们的t是街区数，不可能为0除非没房子，我们最终要求t=target。 初始化 第一栋房子（i=1）： 如果已刷颜色p：则dp[ 1][ p][ 1][ 1 ] = 0（因为第一栋成本为0，且形成一个街区，连续计数1）。 如果未刷：对每种颜色j，dp[ 1][ j][ 1][ 1] = costs[ 0][ j-1 ]。 其他状态初始化为无穷大（表示不可达）。 最终答案 遍历最后一栋房子的颜色j和连续计数c=1~k，取dp[ m][ j][ target][ c ]的最小值。 如果所有都是无穷大，返回-1。 复杂度优化 直接四维dp空间O(m * n * target * k)可能较大，但k通常不大。 可以滚动数组优化第一维（房子），空间O(n * target * k)。 注意：在计算不同色转移时，需要快速找到dp[ i-1][ j'][ t-1][ c']的最小值（对所有j'≠j，c'任意）。可以预处理：对于每个t，维护两个最小值：全局最小值min1（及其颜色j1），和全局次小值min2（颜色j2≠j1）。这样对于当前颜色j，如果j==j1，则用min2，否则用min1。因为我们需要j'≠j的最小值。同时，由于c'维度，我们需要的是所有c'中最小的dp[ i-1][ j'][ t-1][ c']，所以我们可以在计算dp[ i-1]时，对每个(j,t)维护best[ j][ t] = min_ {c'} dp[ i-1][ j][ t][ c' ]，然后用上述min1/min2技巧快速得到不同色转移的最小值。 逐步计算示例 （简化版，便于理解） 假设m=2,n=2,target=2,k=1（即不允许相邻同色！）。 houses=[ 0,0]，costs=[ [ 1,2],[ 3,4] ]。 初始化i=1： dp[ 1][ 1][ 1][ 1]=cost[ 0][ 0 ]=1 dp[ 1][ 2][ 1][ 1]=cost[ 0][ 1 ]=2 i=2（第二栋房子）： 对颜色j=1（cost=3）： 同色转移：需要c>1，但k=1，不允许c=2，所以不考虑。 不同色转移：从前一栋颜色j'=2，t-1=1，c'任意（这里只有1）： dp[ 1][ 2][ 1][ 1]=2，所以dp[ 2][ 1][ 2][ 1 ]=2+3=5。 对颜色j=2（cost=4）： 不同色转移：从前一栋颜色j'=1，t-1=1： dp[ 1][ 1][ 1][ 1]=1，所以dp[ 2][ 2][ 2][ 1 ]=1+4=5。 最终，target=2，取min(dp[ 2][ 1][ 2][ 1], dp[ 2][ 2][ 2][ 1 ])=5。 验证：两栋房子必须不同色才能有2个街区，且相邻不同色满足k=1。最小成本是颜色1然后颜色2：成本1+4=5，或颜色2然后颜色1：成本2+3=5。正确。 实现细节 初始化dp为INF，然后初始化i=1。 从i=2到m循环： 先计算best[ j][ t] = min_ {c} dp_ prev[ j][ t][ c ]。 对每个t，用best数组计算全局最小min1和次小min2。 对当前房子尝试每种颜色j（如果已预刷则只尝试该颜色）： 计算cost_ j。 对t从1到target，c从1到k： a) 同色转移：如果c>1，从dp_ prev[ j][ t][ c-1 ]转移。 b) 不同色转移：如果t>1，从min_ {j'≠j} best[ j'][ t-1 ]转移（利用min1/min2快速得到）。 取a和b的最小值，加上cost_ j，更新dp_ cur[ j][ t][ c ]。 最终答案：min_ {j,c} dp[ m][ j][ target][ c ]，若为INF则-1。 时间复杂度 ：O(m * n * target * k)，但通过min1/min2优化，不同色转移可O(1)完成，所以实际上是O(m * n * target * k)但常数较小。 小结 ：这道题是粉刷房子III的强化版，增加了相邻同色数的限制。关键是在状态中增加连续计数c，并在转移时处理连续与不连续两种情况。利用前缀最小值的技巧优化不同色转移的枚举，从而在合理时间内求解。