粉刷房子 III

在一个小城市里，有 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 个街区。

分析

1. 先通过 houses 和 target 和 n, 分割出可行的街区方案
2. 遍历并计算每一种方案的花费
3. 输出最小的花费

代码

借助深度优先，找出所有可行的切割方案，然后再求出方案花费，计算最小值

var minCost = function(houses, cost, m, n, target) {
    let targetStree = []
    //  dp 使用递归方式 求出 所有的分割方式
    // 上一个房子颜色， 此时街区的数量, 遍历到的位置
    const resDfs = (houseColor, k, postion, res)=>{
        // 此时的颜色
        if(postion > houses.length) return
        if(k > target) return 
        if(k + position < houses.length) return 
        if(postion === houses.length && k === target){    
            targetStree.push([...res])
        }
        if(houses[postion] !== 0){
            res.push(houses[postion])
            if(houseColor === houses[postion]) resDfs(houses[postion],k,postion+1,res)
            else resDfs(houses[postion],k+1,postion+1,res)
            res.pop()
        }else{
            for(let i=1;i<=n;i++){
                res.push(i)
                if(i === houseColor) resDfs(i,k,postion+1,res)
                else resDfs(i,k+1,postion+1,res)
                res.pop()
            }
        }
    }
    if(houses[0] === 0 ){
           let res = []
            for(let i=1;i<=n;i++){
                res.push(i)
                resDfs(i,1,1,res)
                res.pop()
            }
    }
    else resDfs(houses[0],1,1,[houses[0]])
    if(targetStree.length === 0)  return -1
    let resArray = targetStree.map(item => item.reduce((a,b,index)=>{
            if(houses[index] === 0){
                a += cost[index][b-1]
            }
            return a
        }, 0)    
    )
    return Math.min(...resArray)
    
};

算法的时间复杂度和空间复杂度都是(O(nⁿ)), 在数据量比较庞大时，会出现堆栈溢出的情况，所以将递归调用转化成for循环来调用。

官方题解 动态规划

为了方便编码和叙述:

• 房子的编号为 [0, m-1]；
• 颜色的编号为 [0, n-1]，如果房子没有涂上颜色，那么记为 -1；
• 街区的编号为 [0, target−1]。

设 dp(i,j,k) 表示将 [0,i] 的房子都涂上颜色，最末尾的第 i 个房子的颜色为 j，并且它属于第 k 个街区时，需要的最少花费。

状态变换方程

当 i-1 个房子的颜色为j0

• 如果 house[i] !== -1, 说明第 i 个房子已经涂过颜色了, 那 houses[i] === j
  • 当 house[i] !== j,则说明是无效的状态 dp[i][j][k] = ∞
  • 当 house[i] === j
    • 如果 j === j0, 则属于一个街区, dp[i][j][k] = dp[i-1][j][k]
    • 如果 j !== j0, 则不属于一个街区, dp[i][j][k] = min(dp[i-1][j0][k-1])
• 如果 house[i] === -1, 说明第i个房子未涂色, 如果涂上j, 则为 cost[i][j]
  • 如果 j === j0, 则属于一个街区, dp[i][j][k] = dp[i-1][j][k] + cost[i][j]
  • 如果 j !==j0, 则不属于一个街区, dp[i][j][k] = min(dp[i-1][j0][k-1]) + cost[i][j]

最终的答案是: min(dp[m-1][j][target-1])

var minCost = function(houses, cost, m, n, target) {
    houses = houses.map(item => --item)
    const dp = new Array(m).fill(0)
                           .map(() => new Array(n).fill(0)
                           .map(() => new Array(target).fill(Number.MAX_VALUE)));
    // house i 的 循环
    for(let i=0;i<m;i++){
        // color j  的 循环
        for(let j=0;j<n;j++){
            // 如何记录 分区
            if(houses[i] !== -1 && houses[i] !== j) continue
            // 记录每一个 dp(i,j,k) 的 值
            // 当 i 出现时, k值 最大能出现 i个
            for(let k=0;k<=i;k++){
                for(let j0=0;j0<n;j0++){
                    if(j === j0){
                        if(i===0){
                            if(k === 0) dp[i][j][k] = 0
                        }else{
                            dp[i][j][k] = Math.min(dp[i][j][k],dp[i-1][j][k])
                        }
                    }else if(i>0&&k>0){
                        dp[i][j][k] = Math.min(dp[i][j][k],dp[i-1][j0][k-1])
                    }
                }
                if(dp[i][j][k] !== Number.MAX_VALUE && houses[i] === -1) dp[i][j][k] += cost[i][j]
            }  
        }
    }
    let ans = Number.MAX_VALUE
    for(let i=0;i<n;i++){
        if(ans > dp[m-1][i][target-1]) ans = dp[m-1][i][target-1]
    }
    return ans === Number.MAX_VALUE?-1:ans
};

动态规划 优化

参考资料

• leetcode题目链接 (opens new window)
• 官方题解 (opens new window)