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

本文主要是介绍【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

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

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

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

这篇关于【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 删除并获得点数(难度⭐⭐)(76)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/992126

相关文章

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Pyserial设置缓冲区大小失败的问题解决

《Pyserial设置缓冲区大小失败的问题解决》本文主要介绍了Pyserial设置缓冲区大小失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录问题描述原因分析解决方案问题描述使用set_buffer_size()设置缓冲区大小后,buf

resultMap如何处理复杂映射问题

《resultMap如何处理复杂映射问题》:本文主要介绍resultMap如何处理复杂映射问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录resultMap复杂映射问题Ⅰ 多对一查询:学生——老师Ⅱ 一对多查询:老师——学生总结resultMap复杂映射问题