当前位置: 首页 > news >正文

【剑指 の 精选】热门状态机 DP 运用题

题目描述

这是 LeetCode 上的 「剑指 Offer II 091. 粉刷房子」 ,难度为 「中等」

Tag : 「状态机 DP」、「动态规划」

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

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

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

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

示例 1:

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]

输出: 10

解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。

示例 2:

输入: costs = [[7,6,2]]

输出: 2

提示:

状态机 DP

为了方便,我们记 costscs

根据题意,当我们从前往后决策每间房子的颜色时,当前房子所能刷的颜色,取决于上一间房子的颜色。

我们可以定义 为考虑下标不超过 的房子,且最后一间房子颜色为 时的最小成本。

起始我们有 ,代表只有第一间房子时,对应成本为第一间房子的上色成本。

然后不失一般性考虑, 该如何计算: 为所有 (其中 )中的最小值加上

本质上这是一道「状态机 DP」问题:某些状态只能由规则限定的状态所转移,通常我们可以从 能够更新哪些目标状态(后继状态)进行转移,也能够从 依赖哪些前置状态(前驱状态)来转移。

一些细节:考虑到我们 的计算只依赖于 ,因此我们可以使用三个变量来代替我们的动规数组。

Java 代码:

class Solution {
    public int minCost(int[][] cs) {
        int n = cs.length;
        int a = cs[0][0], b = cs[0][1], c = cs[0][2];
        for (int i = 1; i < n; i++) {
            int d = Math.min(b, c) + cs[i][0];
            int e = Math.min(a, c) + cs[i][1];
            int f = Math.min(a, b) + cs[i][2];
            a = d; b = e; c = f;
        }
        return Math.min(a, Math.min(b, c));
    }
}

Java 代码:

class Solution {
    public int minCost(int[][] cs) {
        int n = cs.length;
        int a = cs[0][0], b = cs[0][1], c = cs[0][2];
        for (int i = 0; i < n - 1; i++) {
            int d = Math.min(b, c) + cs[i + 1][0];
            int e = Math.min(a, c) + cs[i + 1][1];
            int f = Math.min(a, b) + cs[i + 1][2];
            a = d; b = e; c = f;
        }
        return Math.min(a, Math.min(b, c));
    }
}
  • 时间复杂度: ,其中 为颜色数量
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 剑指 Offer II 091 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

相关文章:

【剑指 の 精选】热门状态机 DP 运用题

题目描述 这是 LeetCode 上的 「剑指 Offer II 091. 粉刷房子」 &#xff0c;难度为 「中等」。 Tag : 「状态机 DP」、「动态规划」 假如有一排房子&#xff0c;共 n 个&#xff0c;每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种&#xff0c;你需要粉刷所有的房子…...

自动化实践-全量Json对比在技改需求提效实践

1 背景 随着自动化测试左移实践深入&#xff0c;越来越多不同类型的需求开始用自动化测试左移来实践&#xff0c;在实践的过程中也有了新的提效诉求&#xff0c;比如技改类的服务拆分项目或者BC流量拆分的项目&#xff0c;在实践过程中&#xff0c;这类需求会期望不同染色环境…...

【Matlab】PSO优化(单隐层)BP神经网络

上一篇博客介绍了BP-GA&#xff1a;BP神经网络遗传算法(BP-GA)函数极值寻优——非线性函数求极值&#xff0c;本篇博客将介绍用PSO&#xff08;粒子群优化算法&#xff09;优化BP神经网络。 1.优化思路 BP神经网络的隐藏节点通常由重复的前向传递和反向传播的方式来决定&#…...

创建型模式-原型模式

文章目录 一、原型模式1. 概述2. 结构3. 实现4. 案例1.5 使用场景1.6 扩展&#xff08;深克隆&#xff09; 一、原型模式 1. 概述 用一个已经创建的实例作为原型&#xff0c;通过复制该原型对象来创建一个和原型对象相同的新对象。 2. 结构 原型模式包含如下角色&#xff1a; …...

JS逆向系列之猿人学爬虫第11题 - app抓取 - so文件协议破解

题目地址 http://match.yuanrenxue.com/match/11这是个app题目,先下载下来安装到测试手机上 安装完成后的app界面长这样 打开之后是这样的: 要求已经简单明了了。 二话不说先反编译app 不出意外的是没出意外,源代码里面没啥混淆,所有东西都展示的明明白白的。 "…...

c基础扫雷

和三子棋一样&#xff0c;主函数先设计游戏菜单界面&#xff0c;这里就不做展示了。 初始化棋盘 初级扫雷大小为9*9的棋盘&#xff0c;但排雷是周围一圈进行排雷(8格)&#xff0c;而边界可能会越界。数组扩大了一圈,行和列都加了2&#xff0c;所以我们用一个11*11的数组来初始化…...

端点中心(Endpoint Central)的软件许可证管理

软件许可证管理 &#xff08;SLM&#xff09; 是从单个控制台管理整个组织中使用的软件许可证的过程。软件许可证是由软件发行商或分销商制作的法律文件&#xff0c;提供有关软件使用和分发的规则和指南&#xff0c;本文档通常包含条款和条件、限制和免责声明。 软件许可证管理…...

SpringCloud源码探析(九)- Sentinel概念及使用

1.概述 在微服务的依赖调用中&#xff0c;若被调用方出现故障&#xff0c;出于自我保护的目的&#xff0c;调用方会主动停止调用&#xff0c;并根据业务需要进行对应处理&#xff0c;这种方式叫做熔断&#xff0c;是微服务的一种保护方式。为了保证服务的高可用性&#xff0c;…...

nodejs+vue+elementui美食网站的设计与实现演示录像2023_0fh04

本次的毕业设计主要就是设计并开发一个美食网站软件。运用当前Google提供的nodejs 框架来实现对美食信息查询功能。当然使用的数据库是mysql。系统主要包括个人信息修改&#xff0c;对餐厅管理、用户管理、餐厅信息管理、菜系分类管理、美食信息管理、美食文化管理、系统管理、…...

Mysql 数据库增删改查

MySQL是目前最流行的关系型数据库。以下是MySQL数据库的增删改查操作。 1.数据库连接 在进行增删改查操作之前&#xff0c;需要先连接MySQL数据库。使用以下命令进行连接&#xff1a; import mysql.connectormydb mysql.connector.connect(host"localhost",user&…...

【深度学习注意力机制系列】—— ECANet注意力机制(附pytorch实现)

ECANet&#xff08;Efficient Channel Attention Network&#xff09;是一种用于图像处理任务的神经网络架构&#xff0c;它在保持高效性的同时&#xff0c;有效地捕捉图像中的通道间关系&#xff0c;从而提升了特征表示的能力。ECANet通过引入通道注意力机制&#xff0c;以及在…...

python爬虫的简单实现

当涉及网络爬虫时&#xff0c;Python中最常用的库之一是requests。它能够发送HTTP请求并获取网页内容。下面是一个简单的示例&#xff0c;展示如何使用requests库来获取一个网页的内容&#xff1a; import requests 指定要爬取的网页的URL url ‘https://example.com’ 发…...

如何正确的向chatgpt提问?

有没有发现&#xff0c;在使用ChatGPT的时候&#xff0c;他回答的一些问题并不是我们想要的甚至有的时候出现牛头不对马嘴的情况。 这时候就会感慨一句&#xff0c;人工智能也不怎么样嘛! 但是&#xff0c;有没有想过&#xff0c;是自己问的问题太宽泛&#xff0c;没有问到点上…...

一键部署 Umami 统计个人网站访问数据

谈到网站统计&#xff0c;大家第一时间想到的肯定是 Google Analytics。然而&#xff0c;我们都知道 Google Analytics 会收集所有用户的信息&#xff0c;对数据没有任何控制和隐私保护。 Google Analytics 收集的指标实在是太多了&#xff0c;有很多都是不必要的&#xff0c;…...

java种的hutool库接口说明和整理

1. Hutool库基本介绍 1.1. 地址 官网地址&#xff1a;https://www.hutool.cn/ 1.2. 基本介绍 Hutool是一个小而全的Java工具类库&#xff0c;通过静态方法封装&#xff0c;降低相关API的学习成本&#xff0c;提高工作效率&#xff0c;使Java拥有函数式语言般的优雅&#xf…...

控制国外各类电液伺服阀放大器

控制通用型不带反馈信号输入的伺服阀放大器&#xff0c;对射流管式电液伺服阀、喷嘴挡板式电液伺服阀及国外各类电液伺服阀进行控制。 通过系统参数有10V和4~20mA输入指令信号选择&#xff1b; 供电电源: 24VDC&#xff08;标准&#xff09; 输出电流&#xff1a;最大可达10…...

【go语言基础】go中的方法

先思考一个问题&#xff0c;什么是方法&#xff0c;什么是函数&#xff1f; 方法是从属于某个结构体或者非结构体的。在func这个关键字和方法名中间加了一个特殊的接收器类型&#xff0c;这个接收器可以是结构体类型的或者是非结构体类型的。从属的结构体获取该方法。 函数则…...

Go 语言并发编程 及 进阶与依赖管理

1.0 从并发编程本质了解Go高性能的本质 1.1 Goroutine 协程可以理解为轻量级线程&#xff1b; Go更适合高并发场景原因之一&#xff1a;Go语言一次可以创建上万协成&#xff1b; “快速”&#xff1a;开多个协成 打印。 go func(): 在函数前加 go 代表 创建协程; time.Sleep():…...

绽放趋势:Python折线图数据可视化艺术

文章目录 一 json数据格式1.1 json数据格式认识1.2 Python数据和Json数据的相互转换 二 pyecharts模块2.1 pyecharts概述2.2 pyecharts模块安装 三 pyecharts快速入门3.1 基础折线图3.2 pyecharts配置选项3.2.1 全局配置选项 3.4 折线图相关配置3.4.1 .add_yaxis相关配置选项3.…...

BGP小综合

实验要求及拓扑 一、思路 1.使用OSPF使R2-R7之间可通。 2.各自宣告AS区域&#xff0c;两个区域两两之间建邻&#xff0c;AS2两个小区域之间建联邦&#xff08;R2与R5、R4与R7&#xff09;。 3.使R3、R6为路由反射器 RR反射器选取各小区域的路由器作为客户端 、非客户端 4.优…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...