「动态规划」如何求粉刷房子的最少花费?

LCR 091. 粉刷房子icon-default.png?t=N7T8https://leetcode.cn/problems/JEj789/description/

假如有一排房子,共n个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。例如,costs[0][0]表示第0号房子粉刷成红色的成本花费;costs[1][2]表示第1号房子粉刷成绿色的花费,以此类推。请计算出粉刷完所有房子最少的花费成本。

  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

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


我们用动态规划的思想来解决这个问题。

确定状态表示:根据经验和题目要求,我们用dp[i]表示粉刷完i位置的房子后,此时的最少花费。这可以细分为:

  • 用dp[i][0]表示:将i位置的房子粉刷成红色之后的最少花费。
  • 用dp[i][1]表示:将i位置的房子粉刷成蓝色之后的最少花费。
  • 用dp[i][2]表示:将i位置的房子粉刷成绿色之后的最少花费。

简单来说,在dp[i][j]中,i表示最后一个粉刷的房子的编号;j表示最后一个粉刷的房子中,粉刷的颜色的编号;dp[i][j]表示此时的最少花费

推导状态转移方程:我们考虑最近的一步,即粉刷完i - 1位置的房子之后的情况。

  • 考虑dp[i][0]。把i位置的房子粉刷成红色,所以只能把i - 1位置的房子粉刷成蓝色或者绿色。那么,把i位置的房子粉刷成红色之后的最少花费,就应该是把i - 1位置的房子粉刷成蓝色或者绿色之后的最少花费,两种情况的较小值,再加上把i位置粉刷成红色的花费。即dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]。
  • 同理,dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1],dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]。

综上所述:dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0],dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1],dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]

初始化:根据状态转移方程,在计算dp[0][j],其中j的范围是[0, 2]时,会发生越界访问,所以要进行相应的初始化。

  • dp[0][0]表示把0位置的房子粉刷成红色后,此时的最少花费,显然dp[0][0] = costs[0][0]。
  • 同理dp[0][1] = costs[0][1],dp[0][2] = costs[0][2]。

综上所述:dp[0][0] = costs[0][0],dp[0][1] = costs[0][1],dp[0][2] = costs[0][2]

当然,我们可以在最前面添加一个辅助结点dp[0][j] = 0,其中j的范围是[0, 2]。这样,根据状态转移方程,以dp[i][0]为例,此时min(dp[0][1], dp[0][2]) = 0,辅助结点的值不影响结果,符合预期。

填表顺序:根据状态转移方程,对于dp[i][j]只依赖于dp[i - 1][j],j的范围是[0, 2]。那么,我们只需要从左往右填表

返回值:由于不确定把最后一个房子粉刷成什么颜色,根据状态表示,最终应返回把最后一个房子粉刷成红色、蓝色或者绿色这3种情况中,最少花费的最小值,即dp[n][j]的最小值,其中j的范围是[0, 2]。

细节问题:由于新增了一个辅助结点,此时dp表的规模就不是n x 3,而是(n + 1) x 3。同时需注意下标的映射关系,dp[i][j]对应的是costs[i - 1][j]

时间复杂度:O(N),空间复杂度:O(N)。

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();// 创建dp表vector<vector<int>> dp(n + 1, vector<int>(3));// 填表for (int i = 1; i <= n; i++) {dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];}// 返回结果return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/346582.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【全开源】驾校练车管理系统源码(FastAdmin+ThinkPHP)

&#x1f698;驾校练车管理系统&#xff1a;让学车之路更顺畅&#xff01;&#x1f4c8; 一款基于FastAdminThinkPHP开发的驾校管理系统&#xff0c;驾校管理系统(DSS)主要面向驾驶学校实现内部信息化管理&#xff0c;让驾校管理者和工作人员更高效、更快捷的完成枯燥无味的工…

基于JSP的医院远程诊断系统

开头语&#xff1a; 你好呀&#xff0c;我是计算机学长猫哥&#xff01;如果有相关需求&#xff0c;文末可以找到我的联系方式。 开发语言&#xff1a; Java 数据库&#xff1a; MySQL 技术&#xff1a; JSP Servlet JSPBean 工具&#xff1a; IDEA/Eclipse、Navica…

差动放大器

差动器的出现是为了解决直接耦合电路存在的零点漂移问题&#xff0c;另外&#xff0c;差动放大器还有灵活的输入&#xff0c;输出方式。 一&#xff0c;基本差动放大器 差动放大器在电路结构上具有对称性&#xff0c;三极管VT1&#xff0c;VT2同型号&#xff0c;R1R2,R3R4,R5…

MySQL数据库(二)和java复习

一.MySQL数据库学习(二) (一).DQL查询数据 DQL&#xff08;Data Query Language&#xff09;是用于从数据库中检索数据的语言。常见的 DQL 语句包括 SELECT、FROM、WHERE、GROUP BY、HAVING 和 ORDER BY 等关键字&#xff0c;用于指定要检索的数据、数据源、过滤条件、分组方…

20240607每日通信--------VUE3前端引入scoket-io,后端引入Netty-SocketIO,我成功了,希望一起交流沟通

无语 前置&#xff1a; VUE3 前端集成scoket-io socket.io-client Sringboot 3.0JDK17集成Netty-SocketIO Netty-SocketIO 失败原因一&#xff1a; 前期决定要写demo时候&#xff0c;单独了解了&#xff0c;后端引入Netty-SocketIO注意事项&#xff0c;详见我先头写的博客 前…

PCL 生成空间椭圆点云

目录 一、算法原理二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 设椭圆在 X O Y XOY XOY平面上,参数方程为:

【HarmonyOS4学习笔记】《HarmonyOS4+NEXT星河版入门到企业级实战教程》课程学习笔记(十三)

课程地址&#xff1a; 黑马程序员HarmonyOS4NEXT星河版入门到企业级实战教程&#xff0c;一套精通鸿蒙应用开发 &#xff08;本篇笔记对应课程第 20 - 21节&#xff09; P20《19.ArkUI-属性动画和显式动画》 本节先来学习属性动画和显式动画&#xff1a; 在代码中定义动画&am…

蓄电池MSDS报告办理 锂电池运输鉴定中英文报告申请

MSDS 指的是化学产品安全技术说明书 MSDS 报告一般是由工厂所出具的&#xff0c;但也逐渐的应用在各种贸易过程当中&#xff0c;在海运过程当中&#xff0c;相关的产品也需要提供 MSDS 认证报告&#xff0c;不过有些人对于 MSDS 认证所规定的内容不是很了解&#xff0c;接下来大…

Apple开发者macOS设备与描述文件Profile创建完整过程

安装并打开Apple Configurator 新建描述文件 输入macOS平台的描述文件的相关信息,然后选择证书 选择一个可用证书 存储描述文件 存储成功如下: 使用文本编辑器打开刚才保存的描述文件,找到设备名与UDID

绿联Nas docker 中 redis 老访问失败的排查

部署了一些服务&#xff0c;老隔3-5 天其他服务就联不上 redis 了&#xff0c;未确定具体原因&#xff0c;只记录观察到的现象 宿主机访问 只有 ipv6 绑定了&#xff0c;ipv4 绑定挂掉了 其他容器访问 也无法访问成功 当重启容器后&#xff1a; 一切又恢复正常。 可能的解…

简易概况广告变现

广告变现是指媒体或平台通过向用户展示广告主的广告&#xff0c;从而获得收入的过程。 广告变现就像是一个店主&#xff0c;他需要一个吸引人的店面&#xff0c;提供优质的内容和服务&#xff0c;然后在店里摆放一些别人的商品或服务&#xff0c;每当有客人看了或买了这些商品或…

RocketMQ查询出重复数据,两条MessageID一样的解决办法如下

问题描述 在使用RocketMQ的可视化工具dashboard-1.0.0时,首先生产了10条数据,但是查询时却查出来了14条,有四条数据重复,重复数据MessageID和key相同,但是通过key单独查询却只能查出一条 测试代码 package com.fdw.rocketmq.producer;import org.apache.rocketmq.client…

【精通NIO】NIO介绍

一、什么是NIO NIO&#xff0c;全称为New Input/Output&#xff0c;是Java平台中用于替代传统I/O&#xff08;Blocking I/O&#xff09;模型的一个功能强大的I/O API。NIO在Java 1.4版本中被引入&#xff0c;其设计目标是提供一种非阻塞的、低延迟的I/O操作方式&#xff0c;以…

清华出品,开源最强,我又出手了(全网首发!)

清华出品的ChatGLM-6B自开源那刻起&#xff0c;GLM系列的每一次更新都受到了业界的热切关注。尤其是ChatGLM第3代开源之后&#xff0c;其强大和适配性让很多人惊叹&#xff0c;之后大家对GLM的第4代模型充满了期待。终于&#xff0c;今天它来了&#xff01;我要为大家介绍的是这…

【YOLOv5进阶】——修改网络结构(以C2f模块为例)

一、站在巨人的肩膀上 这里我们借鉴YOLOv8源码&#xff1a; 上期说到&#xff0c;对于网络模块定义详情在common.py这个文件&#xff0c;如Conv、CrossConv、C3f等。本期要修改的需要参考YOLOv8里的C2f模块&#xff0c;它定义在YOLOv8的module文件夹的block.py文件里&#xf…

弘君资本股市资讯:增逾20倍!百亿细分龙头利好来了

5月以来&#xff0c;A股进入了时间短的成绩发表空档期&#xff0c;而百亿化工细分龙头齐翔腾达&#xff0c;则以一份高增的成绩预告&#xff0c;摆开半年报成绩预告发表序幕。 6月10日晚间&#xff0c;齐翔腾达发表的成绩预告显现&#xff0c;上半年估计完成归母净赢利1.3亿元…

【渗透测试】|dvwa命令注入乱码问题

法一&#xff1a; 解决方法如下&#xff1a; 1、按住winr&#xff0c;在运行框中输入cmd弹出命令行&#xff0c;在命令行中输入“control intl.cpl” 2、这个命令是使用control命令行工具来打开"区域和语言设置"对话框 3、选中对话框中的管理选项卡 4、可以看到这里…

理解我的积木编程思想

1 学习教程&#xff0c;至少7139手册2 编程实践&#xff0c;遇到实际问题后&#xff0c;在技术资料中查找关键词3 选择适合的条目找到代 码。修正&#xff0c;组合。

git服务器gitblit安装

1、下载 Gitblit 2、下载完后解压&#xff1a; 3、配制&#xff1a; 保存&#xff0c;退出编辑。 4、运行cmd&#xff0c;启用gitblit。 5、根据运行后的提示&#xff0c;也就是我们之间设置的port9990打开&#xff1a; 输入admin,admin就可以登录&#xff0c;这个账号密码&a…

iOS调整collectionViewCell顺序

效果图 原理 就是设置collectionView调整顺序的代理方法&#xff0c;这里要注意一点 调整过代理方法之后&#xff0c;一定要修改数据源&#xff0c;否则导致错乱。 还有就是在collectionView上面添加一个长按手势&#xff0c;在长按手势的不同阶段&#xff0c;调用collectionV…