任县企业做网站,广告创意设计与制作,佛山网站制作哪家,网站设计的逻辑结构文章目录1. 题目2. 解题1. 题目
假如有一排房子#xff0c;共 n 个#xff0c;每个房子可以被粉刷成 k 种颜色中的一种#xff0c;你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然#xff0c;因为市场上不同颜色油漆的价格不同#xff0c;所以房子粉刷成…
文章目录1. 题目2. 解题1. 题目
假如有一排房子共 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) 的时间复杂度下解决此问题来源力扣LeetCode 链接https://leetcode-cn.com/problems/paint-house-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 256. 粉刷房子DP
class Solution {
public:int minCostII(vectorvectorint costs) {if(costs.size()0 || costs[0].size()0)return 0;int m costs.size(), n costs[0].size(), i, c1, c2;vectorvectorint dp(m,vectorint(n,INT_MAX));dp[0] costs[0];for(i 1; i m; i){for(c1 0; c1 n; c1){for(c2 0; c2 n; c2){if(c1c2)continue;dp[i][c2] min(dp[i][c2], dp[i-1][c1]costs[i][c2]);}}}int mincost INT_MAX;for(i 0; i n; i)mincost min(mincost, dp[m-1][i]);return mincost;}
};40 ms 10.5 MB 时间复杂度O(mn2)
可以记录前一个的最小的两个花费和最小花费的颜色降低时间复杂度O(mn)
class Solution {
public:int minCostII(vectorvectorint costs) {if(costs.size()0 || costs[0].size()0)return 0;int m costs.size(), n costs[0].size(), i, c1 -1, c2, mincolor;int prevmin1 0, prevmin2 0, cost, curmin1, curmin2;for(i 0; i m; i){curmin1 curmin2 INT_MAX;for(c2 0; c2 n; c2){cost (c2c1 ? costs[i][c2]prevmin2 : costs[i][c2]prevmin1);//跟前一个最小花费颜色一样加上第二小的。不一样加上最小的if(cost curmin1){curmin2 curmin1;curmin1 cost;mincolor c2;}else if(cost curmin2)curmin2 cost;}prevmin1 curmin1;prevmin2 curmin2;c1 mincolor;}return prevmin1;}
};20 ms 9.8 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
