请选择 进入手机版 | 继续访问电脑版

Leetcode-265 粉刷房子2 题解

[复制链接]
盛夏丨光年丶 发表于 2021-1-2 19:42:58 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题目详情

如果有一排房子,共 n 个,每个房子可以被粉刷成 k 种颜色中的一种,你需要粉刷所有的房子而且使其相邻的两个房子颜色不能相同。
固然,因为市场上差异颜色油漆的代价差异,所以房子粉刷成差异颜色的泯灭资本也是差异的。每个房子粉刷成差异颜色的泯灭是以一个 n x k 的矩阵来表现的。
比方,costs[0][0] 表现第 0 号房子粉刷成 0 号颜色的资本泯灭;costs[1][2] 表现第 1 号房子粉刷成 2 号颜色的资本泯灭,以此类推。请你盘算出粉刷完所有房子最少的泯灭资本。
所有泯灭均为正整数。
示例:
输入: [[1,5,3],[2,9,4]]
输出: 5
表明: 将 0 号房子粉刷成 0 号颜色,1 号房子粉刷成 2 号颜色。最少泯灭: 1 + 4 = 5;
大概将 0 号房子粉刷成 2 号颜色,1 号房子粉刷成 0 号颜色。最少泯灭: 3 + 2 = 5.
要求:O(nk) 的时间复杂度下办理此问题
题目分析

该题是在粉刷房子1的底子上举行的扩展,将颜色的数量扩展到了k,同时加上了一个nk的时间复杂度的限制。
主要的解题分为两部门。
第一部门主要是实现nk2的时间复杂度求解。
这个就是一个dp问题,从第一个房子开始,记载下该房子的每种颜色下的最小消耗。
然后举行迭代,后一个房子要根据前一个房子的颜色,来判定自己粉刷颜色c时,最小消耗。
状态转移方程是:
                               f                      [                      i                      ]                      [                      j                      ]                      =                      m                      i                               n                                   t                            !                            =                            j                                       {                      f                      [                      i                      −                      1                      ]                      [                      0                      ]                      ,                      .                      .                      .                      f                      [                      i                      −                      1                      ]                      [                      t                      ]                      .                      .                      }                      +                      c                      o                      s                      t                      s                      [                      i                      −                      1                      ]                      [                      j                      ]                          f[j] = min_{t!=j}\{f[i-1][0],...f[i-1][t].. \}+costs[i-1][j]               f[j]=mint!=j​{f[i−1][0],...f[i−1][t]..}+costs[i−1][j]
此中可变变量有两个,最小消耗,颜色
如此便可办理nk2的问题
第二部门是从nk2降到nk
这里主要优化点在于k2
按照第一部门的逻辑,当前房子的每种颜色的最小消耗需要去遍历前一个房子的k个颜色的消耗,找到不包罗当前房子颜色的最小值。O(k)
因为有k种颜色,所以就是O(k2)。
针对这个问题,就酿成了,输入k个数的数组,返回一个数组,数组的每个位置值为:撤除当前值的最小值。就酿成了这样一个问题。
针对该问题,我们可以这样来举行办理。对于k个数,我们可以确定的一点是,对于最小值的数,它的位置应该填撤除最小值的次小值。
而对于其他位置,应该填的都是最小值。

那么问题就清晰了,我们只要找到k个数中的最小值,次小值,以及其对应的坐标,那么这个问题就能在O(k)内办理了。
所以该题实际是两个小题目标一个组合。
实现代码

[code]class Solution {    //先写一个nk2的    //大概会出现只有一种颜色,那么这种特殊情况,肯定只有一个房子    //然后如何从k2到k    //有k个值,求除了i之外的最小值(i∈[1,k])    //如果最小值是第i个元素,次小值是第j个元素    //那么除了i之外的最小值是第j个元素    //而除了其他的元素,最小值都是第i个元素    //有趣,这时降为nk    public int minCostII(int[][] costs) {        if(costs==null || costs.length==0)return 0;        if(costs[0].length==1) return costs[0][0];        //创建dp数组并举行初始化        int m = costs.length;        int n = costs[0].length;        int[][] dp = new int[m+1][n];        //举行盘算        for(int i=1; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )