1473. Paint House III¶
题目信息¶
- 题号:
1473
- 难度:
Hard
- 主题:
动态规划、分组、最小成本
- 原题:
- 重点:
已上色房屋不能重涂且不产生费用;相邻同色房屋构成一个街区,要求最终街区数恰为
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,且不能重新上色,只能形成一个街区。