【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 删除并获得点数(难度⭐⭐)(76)

1. 题目解析

题目链接:LCR 091. 粉刷房子

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

2.算法原理

1. 状态定义

在解决这类问题时,我们首先需要根据题目的具体要求来定义状态。针对房屋粉刷问题,我们可以定义一个二维数组dp来表示状态,其中dp[i][j]表示粉刷到第i个位置时,且最后一个位置粉刷成颜色jj可以是红、蓝、绿三种颜色)时的最小花费。

  • dp[i][0]:表示粉刷到第i个位置时,最后一个位置粉刷成红色的最小花费。
  • dp[i][1]:表示粉刷到第i个位置时,最后一个位置粉刷成蓝色的最小花费。
  • dp[i][2]:表示粉刷到第i个位置时,最后一个位置粉刷成绿色的最小花费。
2. 状态转移方程

接下来,我们需要根据题目要求来推导状态转移方程。由于题目中规定了相邻位置不能粉刷成相同的颜色,因此在计算dp[i][j]时,我们需要考虑i-1位置的颜色,并确保与j不同。

  • 对于dp[i][0](即第i个位置粉刷成红色):
    • 由于不能与前一个位置颜色相同,所以前一个位置可以是蓝色或绿色。因此,状态转移方程为:dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0],其中costs[i-1][0]表示第i-1个位置粉刷成红色的花费。
  • 同理,对于dp[i][1]dp[i][2],我们也可以得到相应的状态转移方程:
    • 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]
3. 初始化

在填表之前,我们需要对状态数组进行初始化。由于题目没有明确指出第一个位置之前的颜色,我们可以添加一个辅助节点,并将所有颜色在该节点的花费初始化为0(或者一个不会影响后续计算的值)。这样做可以确保我们的状态转移方程在i=1时也能正确工作。

4. 填表顺序

根据状态转移方程,我们可以发现每个状态dp[i][j]都依赖于前一个位置的状态dp[i-1][k](其中k不等于j)。因此,我们需要按照从左到右的顺序来填表,以确保在计算每个状态时,其依赖的状态已经被计算出来。

5. 返回值

最后,我们需要返回粉刷完整个房屋(即最后一个位置)时的最小花费。由于我们定义了三种颜色的状态,因此需要比较这三种颜色在最后一个位置的最小花费,并返回其中的最小值。即:min(dp[n][0], min(dp[n][1], dp[n][2])),其中n是房屋的总位置数。

3.代码编写

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();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][1], dp[i - 1][0]) + costs[i - 1][2];}return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~

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

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

相关文章

C语言 | Leetcode C语言题解之第85题最大矩形

题目&#xff1a; 题解&#xff1a; int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {int m matrixSize;if (m 0) {return 0;}int n matrixColSize[0];int left[m][n];memset(left, 0, sizeof(left));for (int i 0; i < m; i) {for (int j …

AI图书推荐:ChatGPT 和Power BI驱动未来金融投资变革

《ChatGPT 和Power BI驱动未来金融变革》&#xff08;The Future of Finance with ChatGPT and Power BI&#xff09;由James Bryant和Aloke Mukherjee撰写&#xff0c;探讨了ChatGPT和Power BI在金融领域的应用。 主要特点&#xff1a; - 使用ChatGPT自动化Power BI&#xff…

01 | 为什么需要消息队列?

哪些问题适合使用消息队列来解决&#xff1f; 1. 异步处理 2. 流量控制 使用消息队列隔离网关和后端服务&#xff0c;以达到流量控制和保护后端服务的目的。 3. 服务解耦 无论增加、减少下游系统或是下游系统需求如何变化&#xff0c;订单服务都无需做任何更改&#xff0c…

Linux上编译安装和卸载软件

在maven官网下载maven时候&#xff0c;看到maven-3.9.5这个版本有2份安装包&#xff0c;一个是binaries&#xff0c;一个是source binaries是已编译好的文件&#xff0c;可以直接使用的版本&#xff1b;source是源代码版本&#xff0c;需要自己编译 源码的安装一般由这三个步…

Python函数之旅专栏(导航)

Python内置函数(参考版本:3.11.8)AELRabs( )enumerate( )len( )range( )aiter( )eval( )list( )repr( )all( )exec( )locals( )reversed( )anext( )round( )any( ) ascii( )FM  filter( )map( )S float( )max( )set( )Bformat( )memoryview( )setattr( )bin( )frozenset( )…

Foxmail使用经验总结

目录 1.概述 2.版本历史 3.使用方法 3.1.安装和设置账户 3.2.收取和阅读邮件 ​​​​​​​3.3.发送邮件 ​​​​​​​3.4.管理联系人 ​​​​​​​3.5.日程安排和任务管理 ​​​​​​​3.6.定制设置和插件 ​​​​​​​3.7.跨平台同步 4.小结 1.概述 Fox…

QT:QML制作线形图

目录 一.介绍 二.引入库 三.自定义属性 四.悬停处理函数 五.设置X轴 六.设置Y轴 七.画线 八.测试点坐标 九.设置值 十.效果演示 十一.代码演示 1.LineGraph.qml 2.main.qml 一.介绍 线形图&#xff08;也称为折线图&#xff09;是一种常用的数据可视化工具&#…

Springboot开发 -- Postman 调试 session 验证 接口

当我们在开发Spring Boot应用时&#xff0c;经常会遇到带有Session验证的接口&#xff0c;这些接口需要用户先登录并获取到Session ID&#xff08;或称为cookie中的JSESSIONID&#xff09;&#xff0c;然后在后续的请求中携带这个Session ID来保持会话状态。下面我将以一个实际…

Java 插入数据到Elasticsearch中进行各种类型文档的内容检索

源码下载&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1D3yszkTzjwQz0vFRozQl2g?pwdz6kb 提取码&#xff1a;z6kb 实现思路 1.搭建一个新的springboot项目&#xff0c;不会的请看我这篇博客&#xff1a;springboot项目搭建 2.添加maven依赖 <dependency><…

信息系统项目管理师0602:项目立项管理 — 历年考题(详细分析与讲解)

点击查看专栏目录 1、2017年11月第31题 题干: 项目经理小李依据当前技术发展趋势和所掌握的技术能否支撑该项目的开发,进行可行性研究。小李进行的可行性研究属于( )。 选项: A. 经济可行性分析 B. 技术可行性分析 C. 运行环境可行性分析 D. 其他方面的可行性分析 答案…

远程桌面如何配置?使用快解析远程访问

远程桌面如何设置&#xff1f; 远程桌面作为windows系统内置的一个组件&#xff0c;多年来深受用户喜爱。使用此功能&#xff0c;我们能够轻而易举的控制我们想要控制的电脑。下面我就简单的介绍一下远程桌面的设置方法。 在讲具体设置方法之前&#xff0c;首先应该给大家普及…

6大部分,20 个机器学习算法全面汇总!!建议收藏!(上篇)

前两天有小伙伴说想要把常见算法的原理 公式汇集起来。 这样非常非常方便查看&#xff01;分为上下两篇&#xff0c;下篇地址&#xff1a; 本次文章分别从下面6个方面&#xff0c;涉及到20个算法知识点&#xff1a; 监督学习算法 无监督学习算法 半监督学习算法 强化学习…

PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来

日前&#xff0c;第十二期 CCF 秀湖会议在苏州 CCF 业务总部 & 学术交流中心成功举办。本次会议以“开源教育&#xff1a;使命、挑战与发展”为主题&#xff0c;汇聚了来自学术界、工业界的二十余位专家&#xff0c;共同探讨开源教育的现状与未来。 PingCAP 联合创始人兼 C…

【微信小程序开发(从零到一)【婚礼邀请函】制作】——邀请函界面的制作(2)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

QT多线程的使用

目录 一.介绍 二.第一种多线程方式 1.创建一个线程子类&#xff0c;继承QT中的QThread 2.重新父类的run( )方法 3.在线程中创建子线程对象 4.run( )方法 5.启动子线程 三.第二种多线程方式 1.创建一个新类&#xff08;这个类是QObject的派生&#xff09; 2.在这个类中…

Unity射击游戏开发教程:(18)添加弹药计数+补充弹药

添加简单的弹药计数 我将讨论如何向游戏中添加简单的弹药计数。这将包括在 HUD 中添加弹药计数器,当弹药达到 0 时,文本会将颜色更改为红色以提醒玩家。另外,当弹药数为0时,玩家将无法再射击。让我们深入了解吧! 在播放器脚本中我们需要添加一些变量。我们将创建两个公共整…

Linux 安裝 rpm包

下载 地址&#xff1a;https://developer.aliyun.com/packageSearch 安装 rpm -ivh lsof-4.87-6.el7.x86_64.rpmlsof -Ki|awk {print $2}|sort|uniq -c|sort -nr|head lsof | wc -l

《天空之城》观后感

曾经很长一段时间都着迷于《天空之城》这段旋律&#xff0c;一遍一遍不厌其烦地听&#xff0c;静谧而温馨、豪迈却苍凉&#xff0c;各种复杂的感受随着起伏的音符流淌进心里。多年之后才知道这首曲子出自宫崎骏的同名动画电影。说来也有意思&#xff0c;似乎大多数人是通过电影…

python批量生成防伪识别二维码

欢迎关注我👆,收藏下次不迷路┗|`O′|┛ 嗷~~ 目录 一.前言 二.代码 三.使用 四.总结 一.前言 二维码(QR Code)是一种矩阵条码技术,它使用黑白矩形图案来表示二进制数据,这些矩形图案可以被设备扫描并解读。二维码可以被用来存储

吞吐量 和 延时的关系

关于吞吐量/吞吐率、延时&#xff0c;你可以通过 Jmeter中的”聚合报告“和”用表格查看报告“来获取。 Throughput 越大&#xff0c;Latency 越差&#xff1a;因为请求过多&#xff0c;系统繁忙导致响应速度降低。Latency 的值越小说明能支持的 Throughput 越高&#xff1a;L…