「动态规划」如何求粉刷房子的最少花费?
LCR 091. 粉刷房子
https://leetcode.cn/problems/JEj789/description/
假如有一排房子,共n个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。例如,costs[0][0]表示第0号房子粉刷成红色的成本花费;costs[1][2]表示第1号房子粉刷成绿色的花费,以此类推。请计算出粉刷完所有房子最少的花费成本。
- 输入:costs = [[17,2,17],[16,16,5],[14,3,19]],输出:10,解释:将0号房子粉刷成蓝色,1号房子粉刷成绿色,2号房子粉刷成蓝色。最少花费:2 + 5 + 3 = 10。
- 输入: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]。那么,我们只需要沿着i增大的方向填表。
返回值:由于不确定把最后一个房子粉刷成什么颜色,根据状态表示,最终应返回把最后一个房子粉刷成红色、蓝色或者绿色这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]));}
};相关文章:
「动态规划」如何求粉刷房子的最少花费?
LCR 091. 粉刷房子https://leetcode.cn/problems/JEj789/description/ 假如有一排房子,共n个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然,因为市…...
代码随想录算法训练营DAY41|背包问题 二维 、背包问题 一维、416. 分割等和子集
背包问题 二维 题目链接:背包问题 二维 def bag_weight_problem(n,space,weight,value):dp [[0 for i in range(space1)]for j in range(n)]for i in range(weight[0], space1):dp[0][i]value[0]for j in range(1, n):for k in range(space1):if weight[j]>k:…...
gitlab2024最新版安装
系统:redhat9.0 gitlab版本:gitlab-ce-16.10.7-ce.0.el9.x86_64.rpm 安装组件&包依赖:https://packages.gitlab.com/gitlab/gitlab-ce/packages/ol/9/gitlab-ce-16.10.7-ce.0.el9.x86_64.rpm 参考: 前提: 下载gitl…...
2022C语言二级真题
目录 数组逆序重放 题目描述 样例 最长最短单词 题目描述 样例 统计误差范围内的数 题目描述 样例 有趣的跳跃 题目描述 样例 数字放大 题目描述 样例 内部元素之和 题目描述 样例 满足条件的数的累加 题目描述 样例 偶数降序输出 题目描述 样例 字符统…...
智慧购房:链家网上海在售楼盘数据解析与模型构建
1.项目背景 随着中国经济的快速发展,上海作为国际化大都市,其房地产市场一直备受关注,购房者在面对庞大且复杂的楼盘信息时,往往感到困惑和不知所措,为了帮助购房者更好地了解市场行情,做出明智的购房决策,本项目选择了链家网上海市在售楼盘数据,进行了全面的数据分析…...
二进制数转字符串
题目链接 二进制数转字符串 题目描述 注意点 32位包括输出中的 “0.” 这两位题目保证输入用例的小数位数最多只有 6 位 解答思路 将小数转为二进制的思路是将小数乘2,如果整数部分为1,则说明第i位是1(第i位则乘了2的几次方)…...
WINDOWS系统jdk和maven明明安装了cmd里却无法使用相关命令
今天当了回s b 新电脑jdk和maven装是装了,系统变量也配置了,但没配置完,javahome和mavenhome没配置,结果cmdjdk和maven版本都查不到,我真s b啊 配置 JAVA_HOME 环境变量: 右键点击“此电脑”或者“我的电…...
基于EasyAnimate模型的视频生成最佳实践
EasyAnimate是阿里云PAI平台自主研发的DiT的视频生成框架,它提供了完整的高清长视频生成解决方案,包括视频数据预处理、VAE训练、DiT训练、模型推理和模型评测等。本文为您介绍如何在PAI平台集成EasyAnimate并一键完成模型推理、微调及部署的实践流程。 …...
linux最大线程数限制及打开最大文件数
1.root用户下执行 ulimit -a 然后查看 max user processes 这个值通常是系统最大线程数的一半 max user processes:当前用户同时打开的进程(包括线程)的最大个数为 2.普通用户下 ulimit -a 出现的max user processes的值 默认是 /etc/security/limits.d/20-nproc.co…...
MyBatis系列七: 一级缓存,二级缓存,EnCache缓存
缓存-提高检索效率的利器 官方文档 一级缓存基本介绍快速入门Debug一级缓存执行流程一级缓存失效分析 二级缓存基本介绍快速入门Debug二级缓存执行流程注意事项和使用细节 mybatis的一级缓存和二级缓存执行顺序小实验细节说明 EnCache缓存基本介绍配置和使用EhCache细节说明 My…...
C++迈向精通:函数指针对象与函数对象
C:指针对象 C语言中的函数指针 在C语言中,我们见过如下的函数指针: int add(int a, int b) {return a b; }int main() {int a, b;int (*p)(int, int) add;scanf("%d%d", &a, &b);p(a, b);return 0; } 为了适应C中面向…...
类和对象知识点
面向对象概念回顾 万物皆对象 用程序来抽象(形容)对象 用面向对象的思想来编程 什么是类 基本概念 具有相同特征,具有相同行为,一类事物的抽象。 类是对象的模板,可以通过类创建出对象,类的关键词—…...
【FAS】《Survey on face anti-spoofing in face recognition》
文章目录 原文基于手工设计特征表达的人脸活体检测方法基于深度学习的人脸活体检测方法基于融合策略的人脸活体检测方法人脸检测活体数据库点评 原文 邓雄,王洪春,赵立军等.人脸识别活体检测研究方法综述[J].计算机应用研究,2020,37(09):2579-2585.DOI:10.19734/j.issn.1001-3…...
【Unity】RPG2D龙城纷争(一)搭建项目、导入框架、前期开发准备
更新日期:2024年6月12日。 项目源码:后续章节发布 免责声明:【RPG2D龙城纷争】使用的图片、音频等所有素材均有可能来自互联网,本专栏所有文章仅做学习和教程目的,不会将任何素材用于任何商业用途。 索引 【系列简介】…...
多目标跟踪中检测器和跟踪器如何协同工作的
多目标跟踪中检测器和跟踪器如何协同工作的 flyfish 主要是两者 接口间的交互 假设 原始图像尺寸:1920(宽)x 1080(高) 模型输入尺寸:640(宽)x 640(高) 检…...
kali系统几个开机启动项的区别
1、Live system (amd64) 简单的模式 ,启动系统,直接进入 Kali,在系统中的所有的操作和设置都会在下次重启时失效。 Kali 中保存/编辑的所有东西都会重启丢失。 2、Live system (amd64 fail-safe mode) 这种模式与 Live (amd64) 类似…...
【自撰写】【国际象棋入门】第5课 常见开局战术组合(一)
第5课 常见开局战术组合(一) 本次课中,我们简要介绍几种常见的开局战术组合。开局当中,理想的情况是,己方的两只(或以上)轻子相互配合,或者与己方的兵配合,在完成布局的…...
高考志愿填报选专业,女孩就业率最好的专业有哪些?
高考志愿填报选专业, 大家都会关心:将来怎么就业? 按照目前的环境来说,女孩的就业是不乐观的,在职场上,绝大部分岗位都是男性优先的,至少短期内可能还无法改变,这样就要求我们在大学…...
yolov5模型训练早停模型变大
目录 1. 背景2. 原因分析2.1 train代码分析2.2 strip_optimizer函数分析 3. 验证 1. 背景 最近使用tph-yolov5训练yolov5l-tph-plus模型时,发现模型收敛的差不多了,就果断的停止了训练,结果发现last.pt和best.pt竟然488M,而正常训…...
next是什么???
大家都知道最近出了一个很火的框架,Next.js框架。很多大公司(例如:Tencent腾讯,docker,Uber)的项目都在使用这个Next.js框架。那Next.js到底是一个什么框架呢?Next.js有什么优点呢?今…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
