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``。 自建示例 -------- 不同颜色可形成两个街区: .. code-block:: text 输入:houses = [0,0], cost = [[1,5],[5,1]], m = 2, n = 2, target = 2 输出:2 解释:分别涂成颜色 1 和 2,形成两个街区,总费用为 1 + 1。 已有同色房屋无法被拆成更多街区: .. code-block:: text 输入:houses = [1,1], cost = [[1,1],[1,1]], m = 2, n = 2, target = 2 输出:-1 解释:两栋房屋均已涂成颜色 1,且不能重新上色,只能形成一个街区。