LintCode刷题笔记-- PaintHouse 1&2
标签:
动态规划
题目描述:
There are a row of n
houses, each house can be painted with one of the k
colors. 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 k
cost matrix. For example,costs[0][0]
is the cost of painting house 0
with color 0
; costs[1][2]
is the cost of painting house 1
with color 2
, and so on... Find the minimum cost to paint all houses.
Example
Given n
= 3, k
= 3, costs
=[[14,2,11],[11,14,5],[14,3,10]]
return 10
house 0 is color 2, house 1 is color 3, house 2 is color 2,2 + 5 + 3 = 10
解题思路:
这两题较比之前的题目来讲要简单很多,子状态非常明显,转移方程非常容易得到
1.对于每一个房子,都k种设计方案。第n间房子的每种颜色的方案依赖于,第n-1间房子的其他颜色的最省钱方案。
2.初始状态,只有一间房子的时候,颜色价格方案是已知的。
参考代码:
public int minCostII(int[][] costs) {
// Write your code here
if(costs.length == 0||costs[0].length == 0) return 0;
int n = costs.length;
int k = costs[0].length; int[][] dp = new int[n][k];
for(int i = 0; i<k; i++){
dp[0][i] = costs[0][i];
} for(int i=1; i<n; i++){
for(int j = 0; j<k; j++){
int tmp_min = Integer.MAX_VALUE;
for(int m = 0; m<k; m++){
if(m==j){
continue;
}else{
tmp_min = Math.min(tmp_min, dp[i-1][m]);
}
}
dp[i][j] = tmp_min+costs[i][j];
}
} int min = Integer.MAX_VALUE;
for(int i=0; i<k; i++){
min = Math.min(min, dp[n-1][i]);
} return min;
}
最新文章
- 触发Full GC执行的情况
- openstack instance snapshort
- 点击listview 的列头对其item进行自动排序
- CPU,MPU,MCU,SOC,SOPC联系与差别
- zoj 1610 Count the Colors(线段树延迟更新)
- gameUnity 0.15alpha 网络游戏框架
- 第一个远程javaweb项目测试全过程
- nopCommerce 3.9 大波浪系列 之 IWebHelper
- XSS分析及如何预防
- MongoDB学习教程(1)
- Spring IOC容器分析(2) -- BeanDefinition
- 三、TensorFlow模型的保存和加载
- 宋宝华:关于Ftrace的一个完整案例【转】
- Java高并发--AQS
- goLand工程结构管理
- 用GDB调试程序(六)
- android AsyncHttpClient使用
- 20172302 《Java软件结构与数据结构》第四周学习总结
- [au3]复制选择性粘贴文本到excel
- Entity Framework 6.1.0 Tools for Visual Studio 2012 &; 2013