LintCode 房屋染色题目代码

题目

这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小。

费用通过一个nx3 的矩阵给出,比如cost[0][0]表示房屋0染红色的费用,cost[1][2]表示房屋1染绿色的费用。

** 注意事项** 所有费用都是正整数

样例 costs = [[14,2,11],[11,14,5],[14,3,10]] return 10 房屋 0 蓝色, 房屋 1 绿色, 房屋 2 蓝色, 2 + 5 + 3 = 10

代码

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) {
        if(costs != null && costs.length == 0) return 0;
        for(int i=1;i<costs.length;i++) {
            // 涂第一种颜色的话,上一个房子就不能涂第一种颜色,这样我们要在上一个房子的第二和第三个颜色的最小开销中找最小的那个加上
            costs[i][0] = costs[i][0] + Math.min(costs[i-1][1], costs[i-1][2]);
            // 涂第二或者第三种颜色同理
            costs[i][1] = costs[i][1] + Math.min(costs[i-1][0], costs[i-1][2]);
            costs[i][2] = costs[i][2] + Math.min(costs[i-1][1], costs[i-1][0]);
            
        }
        // 返回涂三种颜色中开销最小的那个
        return Math.min(Math.min(costs[costs.length-1][0], costs[costs.length-1][1]), costs[costs.length-1][2]);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Flutter入门

Android OpenGL ES(三)-平面图形

前两章,其实我们已经明白了绘制平面图形的套路了。 接下来我们按照套路继续画其他的图形。

29730
来自专栏ACM算法日常

翻转瓷砖Fliptile(开关反转)- POJ 3279

Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

11720
来自专栏数据结构与算法

BZOJ4518: [Sdoi2016]征途(dp+斜率优化)

Description Pine开始了从S地到T地的征途。 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m...

39480
来自专栏每日一篇技术文章

OpengL ES _ 入门_02

顶点是啥? 顶点就是坐标位置,不管你是画直线,三角形,正方体,球体,以及3D游戏人物等,都需要顶点来确定其形状。 顶点坐标创建 1.记住顶点的坐标数据类型...

13110
来自专栏数据结构与算法

BZOJ 5248: [2018多省省队联测]一双木棋(对抗搜索)

15700
来自专栏BestSDK

10行代码告诉你,为什么说Python数据可视化是一件艺术品

1. 画散点图 画散点图用plt.scatter(x,y)。画连续曲线在下一个例子中可以看到,用到了plt.plot(x,y)。 plt.xticks(loc,...

43960
来自专栏desperate633

LintCode 接雨水题目分析方法三

给出 n 个非负整数,代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少(面积)雨水。

19920
来自专栏林德熙的博客

Latex 公式速查

所有的在 Latex 使用的字符公式,都需要放在\(和\),$ 和 $,\begin{math} 和\end{math}之间。

66330
来自专栏数据结构与算法

1004 四子连棋 未完成

1004 四子连棋  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descriptio...

28040
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 4: 3D Spaces_Direct3D 11 教程4:3D空间

在上一个教程中,我们在应用程序窗口的中心成功渲染了一个三角形。 我们没有太注意我们在顶点缓冲区中拾取的顶点位置。 在本教程中,我们将深入研究3D位置和转换的细节...

13530

扫码关注云+社区

领取腾讯云代金券