256. Paint House房屋染色
[抄题]:
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x 3
cost matrix. For example, costs[0][0]
is the cost of painting house 0 with color red; costs[1][2]
is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
[暴力解法]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
[思维问题]:
以为要用i , j的二维矩阵:就3种情况,枚举所有情况就行了
[一句话思路]:
求和取前一步最小值,从而实现步步最小
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- 理解过程:把所有值都累加到nums[n]中
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
求和类型的三步dp,套用坐标型模板
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
[关键模板化代码]:
标准格式i = 0,i < n,return f[n - 1]
for (int i = 1; i < n; i++) {
costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
}
//answer
return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1],costs[n - 1][2]));
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
265. Paint House II 数学问题,感觉并没有什么联系
[代码风格] :
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) {
//corner case
if (costs.length == 0 || costs[0].length == 0) {
return 0;
}
//get sum
int n = costs.length;
for (int i = 1; i < n; i++) {
costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
}
//answer
return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1],costs[n - 1][2]));
}
}
最新文章
- PHPCMS企业站制作
- Jqgrid学习API
- c#中如何获取listbox中选中值的问题
- Firemonkey TComboBox 下拉菜单字型修改方法 (D10)
- Noip2000 T3 单词接龙
- DMSFrame 之SqlCacheDependency(一)
- [CareerCup] 13.5 Volatile Keyword 关键字volatile
- 前端测试框架 jasmine 的使用
- C# 函数覆盖总结学习
- .NET 互操作
- USB Loader使用心得之游戏名称、简介、背景音乐
- 果园种植系统开发App,游戏+商业模式?
- cut的用法
- 【NOIP2016提高组】换教室
- Linux系统的启动过程
- 适配器模式 adapter 结构型 设计模式(九)
- java调用matlab
- 操作系统口令认证,sysdba本地登录需要输入密码
- MySQL Export--导出数据
- avalon1与avalon2的异同点