【LeetCode】粉刷房子 Java 题解
题目描述
假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推。
请计算出粉刷完所有房子最少的花费成本。
复制代码
思路分析
今天的算法题目是粉刷房子题目,题目比较长。重点如下。
题目给出的是 costs 数组,代表刷一个房子,使用不同颜色,需要不同的花费。
粉刷房子的时候,需要使其相邻的两个房子颜色不相同。
我们需要求解的是粉刷房子的最小花费。
根据上述关键点的分析,我们可以采用动态规划思想来做这个题目。动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
具体到这个题目子问题就是求解每一层的粉刷花费。就是关键点 2。我们初始化二维 DP 数组,这个题目只有 3 种颜色。直接使用 cost[0][0],cost[0][1],cost[0][2] 初始化。由于相邻房子颜色不能相同。动态转移方程为
复制代码
dp 方程计算完成之后,找出最小值就是答案。具体实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/184f82b513d544ddde3d794c9】。文章转载请联系作者。
评论