大厂面试真题详解:房屋染色-阿里云开发者社区

开发者社区> 算法编程> 正文

大厂面试真题详解:房屋染色

简介: 大厂面试真题详解:房屋染色

这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小,返回最小的费用。
费用通过一个nx3 的矩阵给出,比如cost0表示房屋0染红色的费用,cost1表示房屋1染绿色的费用。

在线评测地址:领扣题库官网

样例 1:

输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 第一个屋子染蓝色,第二个染绿色,第三个染蓝色,最小花费:2 + 5 + 3 = 10.

样例 2:

输入: [[1,2,3],[1,4,6]]
输出: 3

算法:动态规划(dp)

算法思路

  • dpi表示第i幢房子涂j的颜色最小的花费总和,即从前一幢房子的状态dp[i-1]k中选一个不同颜色且最小的再加上给第i幢房子涂j颜色的costs。

代码思路

  1. 初始化状态dp0=costs0
  2. 从左往右遍历每一幢房子,计算到该幢房子涂每种颜色的最小花费,状态转移方程是dpi = min{dpi-1 +costsi} (k != j)
  3. 答案为到最后一幢房子涂每种颜色花费中的最小值,即min(dpn-1),k=0,1,2

复杂度分析

N表示房子的幢数,即costs数组长度

  • 空间复杂度:O(1)
  • 时间复杂度:O(N)
    优化
  • 滚动存储状态,可以将空间复杂度从O(N)优化到O(1)。

代码

public class Solution {

    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */

    public int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) {
            return 0;
        }

        //dp[i][j]表示第i幢房子涂j的颜色最小的总和
        //初始化状态dp[0][i]=costs[0][i]

        int[][] dp = new int[2][3];

        for (int i= 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i&1][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (k != j) {
                        dp[i&1][j] = Math.min(dp[i&1][j], dp[i&1^1][k] + costs[i][j]);
                    }
                }
            }
        }
        return Math.min(dp[n&1^1][0], Math.min(dp[n&1^1][1], dp[n&1^1][2]) );
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接