一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1080|回复: 5
收起左侧

[算法题] 求lc Paint House II的O(nk)解法

[复制链接] |试试Instant~ |关注本帖
zws0818 发表于 2015-8-20 07:30:04 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
求地里大神能给一下解答,目前小弟只想到用DP的解法但是复杂度是O(nk^2), 目前能想到的改进成nk的方法是用bucket sort,但是太渣,不会写桶排序,求大神指导
jiebour 发表于 2015-8-21 07:38:48 | 显示全部楼层
一天了,没人回复。。。。
回复 支持 反对

使用道具 举报

flamen 发表于 2015-8-21 08:21:30 | 显示全部楼层
DP为啥是O(nk^2)? 难道不是O(nk)?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-8-21 08:23:06 | 显示全部楼层
public int minCostII(int[][] costs){
                if(costs == null || costs.length == 0 || costs[0].length <= 1){
                        return 0;
                }
                int k = costs.length;
                int n = costs[0].length;
                int firstIndex = -1;
                int first = 0;
                int second = 0;
                for(int i=1;i<n;i++){
                        int newFirst = Integer.MAX_VALUE;
                        int newSecond = Integer.MAX_VALUE;
                        int newFirstIndex = -1;
                        for(int j=0;j<k;j++){
                                int cur = costs[j][i];
                                costs[j][i] = cur + (firstIndex == j? second:first);
                                if(costs[j][i] < newFirst){
                                        newSecond = newFirst;
                                        newFirst = costs[j][i];
                                        newFirstIndex = j;
                                }
                                else if(costs[j][i] < newSecond){
                                        newSecond = costs[j][i];
                                }
                        }
                        first = newFirst;
                        firstIndex = newFirstIndex;
                        second = newSecond;
                }
                return first;
        }
写了一个,因为没有买premium,所以不知道能不能AC,只是提供一下自己的思路,也不知道对不对,求讨论。
用DP,如果不能改变costs[][]的值,就新create一个matrix,cost[j][i]表示第i个房子刷第k种颜色,前i个房子最少的cost,记录firstIndex是为了满足相邻房子不能刷同种颜色的条件。
可能会有bug,
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-21 08:39:35 | 显示全部楼层
宝贝忆彼岸 发表于 2015-8-21 08:23
public int minCostII(int[][] costs){
                if(costs == null || costs.length == 0 || costs[0].length

复杂度是多少?nk?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-8-21 09:16:41 | 显示全部楼层
jiebour 发表于 2015-8-21 08:39
复杂度是多少?nk?

是的 字。。。。。。。数
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 02:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表