【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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错