leetcode 剑指 Offer II 091. 粉刷房子

这篇具有很好参考价值的文章主要介绍了leetcode 剑指 Offer II 091. 粉刷房子。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:leetcode 剑指 Offer II 091

1.题目

假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推。

请计算出粉刷完所有房子最少的花费成本。

2.示例

1)示例 1:
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。

2)示例 2:
输入: costs = [[7,6,2]]
输出: 2

3)提示:
costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20

3.分析

可以发现是一个比较简单的dp问题,以f[i][j]为前i个房子已经完成涂色,并且第i个房子的颜色为j的最小花费,那么考虑前i+1个房子,那第i+1个房子的颜色必须与第i个房子不同,那么f[i+1][k]=min(f[i+1][k],f[i][j]+costs[i+1][k])(j≠k)文章来源地址https://www.toymoban.com/news/detail-501370.html

4.代码

class Solution {
public:
    int f[110][4];
    map<int,vector<int>> map1;
    int minCost(vector<vector<int>>& costs) {
        memset(f,10,sizeof(f));
        for(int i=0;i<3;i++){
            f[0][i]=costs[0][i];
            for(int j=0;j<3;j++)
                if(j!=i)
                    map1[i].push_back(j);
        }
        for(int i=1;i<costs.size();i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<map1[j].size();k++){
                    int color=map1[j][k];
                    f[i][color]=min(f[i][color],f[i-1][j]+costs[i][color]);
                }
                    
        int ans=f[costs.size()-1][0];
        for(int i=0;i<3;i++)
            ans=min(ans,f[costs.size()-1][i]);
        return ans;
    }
};

到了这里,关于leetcode 剑指 Offer II 091. 粉刷房子的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (贪心) 剑指 Offer 14- II. 剪绳子 II ——【Leetcode每日一题】

    难度:中等 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段( m 、 n 都是整数, n 1 并且 m 1 ),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最

    2024年02月13日
    浏览(48)
  • LeetCode:剑指 Offer 58 - II. 左旋转字符串

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串\\\"abcdefg\\\"和数字2,该函数将返回左旋

    2024年02月02日
    浏览(46)
  • Leetcode-每日一题【剑指 Offer 32 - II. 从上到下打印二叉树 II】

    从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。 例如: 给定二叉树:  [3,9,20,null,null,15,7] ,     3    /   9  20     /     15   7 返回其层次遍历结果: [   [3],   [9,20],   [15,7] ] 提示: 节点总数 = 1000 1.题目要求我们从上到下按层打印二

    2024年02月12日
    浏览(43)
  • Leetcode-每日一题【剑指 Offer II 010. 和为 k 的子数组】

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况 示例 2: 输入: nums = [1,2,3], k = 3 输出: 2 提示: 1 = nums.length = 2 * 104 1000 = nums[i] = 1000 107 = k = 107 前置知识 前缀和

    2024年02月15日
    浏览(47)
  • (字符串 ) 剑指 Offer 58 - II. 左旋转字符串 ——【Leetcode每日一题】

    难度:简单 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串\\\"abcdefg\\\"和数字2,该函数将返回左旋转两位得到的结果\\\"cdefgab\\\"。 示例 1: 输入: s = “abcdefg”, k = 2 输出: “cdefgab” 示例 2:

    2024年02月08日
    浏览(45)
  • 【LeetCode: 剑指 Offer II 089. 房屋偷盗(打家窃舍) | 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 剑指 Offer II 089. 房屋偷盗

    2024年02月02日
    浏览(45)
  • 【LeetCode: 剑指 Offer II 090. 环形房屋偷盗(打家窃舍) | 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 大家再看这道题目之前,

    2023年04月14日
    浏览(43)
  • 剑指 Offer 34. 二叉树中和为某一值的路径 / LeetCode 113. 路径总和 II(深度优先搜索)

    链接:剑指 Offer 34. 二叉树中和为某一值的路径;LeetCode 113. 路径总和 II 难度:中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,1

    2024年02月03日
    浏览(38)
  • 剑指 Offer II 024. 反转链表(经典题型)

    时间是伟大的作者,她能写出未来的结局。                               ——卓别林 目录 题目描述: 方法1:迭代法(翻指针) 方法2:头插法  方法3:递归法  给定单链表的头节点 head ,请反转链表, 并返回反转后的链表的头节点 。 示例 1: 输入:head = [1,2,3,4,5]

    2023年04月09日
    浏览(35)
  • 剑指 Offer II 010. 和为 k 的子数组

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 示例 2: 提示: 这个题目做出来不难,直接暴力枚举。但是利用哈希表和前缀和优化的过程我一直不是很理解,所以写下这篇文章来一点一点的研究,希望能对大家有所帮助 首先,先看最

    2023年04月16日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包