X

LEETCODE 1473. Paint House III 解题思路分析

题目大意:

给房子涂色 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 个街区。

提示:

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1473

解题思路分析:

这种题目我们很难一眼看出答案,必须尝试每一种组合方式来找到一个最优解。对于这种问题最高效的方式就是使用动态规划DP,来遍历每一种情况,进而从中找到最优方案。对于DP问题我更习惯使用递归加记忆数组的方式,本题我们也会采用递归方式来做讲解。

  1. 建立递归方法,定义三个方法参数,分别是当前房屋下标index,尚未分组个数target,相邻前一个房子的颜色lastColor。
  2. 递归中,如果target小于0,返回-1。如果index等于房屋数量,证明已递归完所有房屋,此时查看target是否正好等于0,如果不是,说明没有将所有房屋分为target个街区,返回-1,反之返回0。
  3. 如果当前房屋已经存在颜色(houses[index]>0),我们无须再上色,因此也不会产生cost。这时需要判断当前颜色是否与前一栋房子颜色lastColor相同,如果相同,代表他们是同一街区,即target不变。反之,说明当前房屋不属于上一个街区,换句话说它是一个新街区的起点,此时target减一。另外将index加一,并将当前房屋颜色作为lastColor传入递归函数(递归至下一栋房屋),返回结果即是当前递归的返回结果。
  4. 如果当前房屋没有颜色(houses[index]==0),那么我们就需要在所有颜色中选择一种为他涂色,因为我们无法得知选择哪一种颜色能使得全局花费最小,因此需要尝试每一种选择,所有选择中总花费最小的即是当前返回结果。我们循环每一种颜色,首先查看当前颜色是否等于前一栋房子颜色lastColor,如果相同target不变。反之target-1。另外将index加一,并将当前房屋颜色作为lastColor传入递归函数(递归至下一栋房屋)。如果递归函数的返回值是-1,代表当前选择无法产生一个合理解,跳过,继续循环到下一种颜色。如果递归函数能够返回一个合理解,那么再加上当前涂色的费用,这既是一个合理解,用该合理解更新当前递归的最小值。循环完所有颜色后,最小值即是本层递归的返回值。
  5. 上述递归实际上是暴力枚举每一种涂色方式,然后通过局部最优一步一步推出全局最优。对于暴力枚举,必将会产生大量重复计算,因此我们需要使用一个记忆数组来记录已经计算过的数值,避免重复计算从而提高效率。递归函数中存在3个变量,所以我们需要建立一个三维数组来记录递归函数的返回值(具体参照代码)。

实现代码:

Integer[][][] memo; // 记忆数组
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
    memo=new Integer[m][target+1][n+1]; // 初始化记忆数组
    return help(houses,cost,0,target,0); // 递归求解
}

int help(int[] houses, int[][] cost, int index, int target, int lastColor){
    if(target<0) return -1; // 如果target小于0,返回-1。
    // 递归完所有下标后,若target正好等于0,返回0,反之返回-1
    if(index==houses.length) return target==0?0:-1;
    // 如果记忆数组中存在当前解,直接返回
    if(memo[index][target][lastColor]!=null) return memo[index][target][lastColor];
    // 当前房屋已经上色
    if(houses[index]>0){
        // 当前颜色
        int color=houses[index];
        // 如果与上一间房屋颜色不同,开启新街区,target减一
        if(color!=lastColor)target--;
        // 递归至下一房屋
        return help(houses,cost,index+1,target,color);
    }
    // 最小化费
    int min=Integer.MAX_VALUE;
    // 循环每一种颜色
    for(int c=1;c<=cost[0].length;c++){
        // 递归至下一件房屋
        int costTemp=help(houses,cost,index+1,c==lastColor?target:target-1,c);
        // 递归函数如果返回-1,代表选择当前颜色不会产生合理解,跳过
        if(costTemp==-1) continue;
        // 递归函数结果加上当前花费
        costTemp+=cost[index][c-1];
        // 更新全局最小化费
        min=Math.min(min,costTemp);
    }
    // 如果没找到合理解,min设置为-1
    if(min==Integer.MAX_VALUE) min=-1;
    // 将结果保存至记忆数组
    memo[index][target][lastColor]=min;
    return min;
}

本题解法执行时间为40ms。

Runtime: 40 ms, faster than 30.05% of Java online submissions for Paint House III.

Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Paint House III.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1473-paint-house-iii-解题思路分析/
Categories: leetcode
kwantong: