1473. Paint House III

题目信息

题号:

1473

难度:

Hard

主题:

动态规划、分组、最小成本

原题:

LeetCode 1473

重点:

已上色房屋不能重涂且不产生费用;相邻同色房屋构成一个街区,要求最终街区数恰为 target

题目重述

街道上有 m 栋房屋和 n 种颜色。houses[i] == 0 表示房屋未上色,否则其值是已有颜色编号。cost[i][j] 表示把未上色的第 i 栋房屋涂成颜色 j+1 的费用。

相邻且颜色相同的连续房屋构成一个街区。请把所有未上色房屋完成上色,使街区数量恰好为 target,并返回最小费用;无法做到时返回 -1。

1 <= m <= 100,1 <= n <= 20,1 <= target <= m。

自建示例

不同颜色可形成两个街区:

输入:houses = [0,0], cost = [[1,5],[5,1]], m = 2, n = 2, target = 2
输出:2
解释:分别涂成颜色 1 和 2,形成两个街区,总费用为 1 + 1。

已有同色房屋无法被拆成更多街区:

输入:houses = [1,1], cost = [[1,1],[1,1]], m = 2, n = 2, target = 2
输出:-1
解释:两栋房屋均已涂成颜色 1,且不能重新上色,只能形成一个街区。