当前位置:网站首页>LeetCode_2598_剑指Offer Ⅱ 091.粉刷房子
LeetCode_2598_剑指Offer Ⅱ 091.粉刷房子
2022-08-10 14:43:00 【Fitz1318】
题目链接
题目描述
假如有一排房子,共 n
个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3
的正整数矩阵 costs
来表示的。
例如,costs[0][0]
表示第 0
号房子粉刷成红色的成本花费;costs[1][2]
表示第 1
号房子粉刷成绿色的花费,以此类推。
请计算出粉刷完所有房子最少的花费成本。
示例 1:
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。
示例 2:
输入: costs = [[7,6,2]]
输出: 2
提示:
costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20
解题思路
动态规划
确认dp数组及下标的含义
dp[i][k]
:粉刷前i
个房子且第i
个房子被粉刷成第k
中颜色时的最小花费成本
确定递推公式
- 如果第i个房子被粉刷成第0种颜色时,则
dp[i][0]
可以由两个状态推导出来- 如果第i-1个房子被粉刷成第1种颜色,由于相邻的颜色不能一样,所以
dp[i][0] = dp[i-1][1] + costs[i][0]
- 如果第i-1个房子被粉刷成第2种颜色,由于相邻的颜色不能一样,所以
dp[i][0] = dp[i-1][2] + costs[i][0]
- 综上,
dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + costs[i][0]
- 如果第i-1个房子被粉刷成第1种颜色,由于相邻的颜色不能一样,所以
- 如果第i个房子被粉刷成第1种颜色时,则
dp[i][1]
可以由两个状态推导出来- 如果第i-1个房子被粉刷成第0种颜色,由于相邻的颜色不能一样,所以
dp[i][1] = dp[i-1][0] + costs[i][1]
- 如果第i-1个房子被粉刷成第2种颜色,由于相邻的颜色不能一样,所以
dp[i][0] = dp[i-1][2] + costs[i][1]
- 综上,
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + costs[i][1]
- 如果第i-1个房子被粉刷成第0种颜色,由于相邻的颜色不能一样,所以
- 如果第i个房子被粉刷成第2种颜色时,则
dp[i][2]
可以由两个状态推导出来- 如果第i-1个房子被粉刷成第0种颜色,由于相邻的颜色不能一样,所以
dp[i][2] = dp[i-1][0] + costs[i][2]
- 如果第i-1个房子被粉刷成第1种颜色,由于相邻的颜色不能一样,所以
dp[i][2] = dp[i-1][1] + costs[i][2]
- 综上,
dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1]) + costs[i][2]
- 如果第i-1个房子被粉刷成第0种颜色,由于相邻的颜色不能一样,所以
dp数组初始化
dp[0][k] = costs[0][k]
确定遍历顺序
- 从前往后遍历
AC代码
class Solution {
public int minCost(int[][] costs) {
int len = costs.length;
int[][] dp = new int[len][3];
for (int i = 0; i < 3; i++) {
dp[0][i] = costs[0][i];
}
for (int i = 1; i < len; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
}
return Math.min(dp[len - 1][0], Math.min(dp[len - 1][1], dp[len - 1][2]));
}
}
边栏推荐
猜你喜欢
随机推荐
兆骑科创创业赛事活动发布平台,创业赛事,项目路演
Lilac Garden
【有限元分析】异型密封圈计算泄漏量与参数化优化过程(带分析源文件)
Second half of 2011 System Architect Afternoon Paper II
How to code like a pro in 2022 and avoid If-Else
面试面到了一个腾讯30k出来的,有见识到何为精通MySQL调优
数学建模学习视频及资料集(2022.08.10)
【语义分割】DeepLab系列
静态变量存储在哪个区
Parallels 将扩展桌面平台产品,以进一步改善在 Mac 上运行 Windows 的用户体验和工作效率
蓝帽杯半决赛火炬木wp
符合信创要求的堡垒机有哪些?支持哪些系统?
线上线下课程教学培训小程序开发制作功能介绍
网络初识(二)
epoll学习:思考一种高性能的服务器处理框架
“国资云”和“国家云”能给市场带来怎样的变革?
file system design
redhat替换yum源时redhat.repo无法删除或无法禁用的问题解决方法
正则表达式(包含各种括号,echo,正则三剑客以及各种正则工具)
《论文阅读》PLATO: Pre-trained Dialogue Generation Model with Discrete Latent Variable