动态规划 —— dp 问题-粉刷房子

1. 剑指offer —— 粉刷房子

题目链接:

LCR 091. 粉刷房子 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/JEj789/description/

 


2. 题目解析

根据上图可以得到costs横坐标(行)是房子的号数,红色的下标是0,蓝色的下标是1,绿色的下标是2,粉刷房子只需要保证相邻的两个颜色不同就行


3.  算法原理 

状态表示:以某一个位置为结尾或者以某一个位置为起点

   

dp[i][0]表示:涂到i位置的时候,最后一个位置粉刷红色,此时的最小花费分

  

dp[i][1]表示:涂到i位置的时候,最后一个位置粉刷蓝色,此时的最小花费分

   

dp[i][2]表示:涂到i位置的时候,最后一个位置粉刷绿色,此时的最小花费分

2. 状态转移方程

  

根据最近的一步来划分问题:

   

1. dp[i][0]=min(dp[i-1][1] , dp[i-1][2]) + costs[i][0]

   

2. dp[i][1]=min(dp[i-1][0] , dp[i-1][2]) + costs[i][1]

   

3. dp[i][2]=min(dp[i-1][1] , dp[i-1][0]) + costs[i][2]

   

3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行

    

我们可以在前面再额外的加上一个虚拟节点   

本题初始化为:0

  

本题的下标映射关系:因为本题给了一个数组,而我们又额外的加上一个虚拟节点 ,所以我们的下标都统一往右边移动了一位,如果想找回之前对应的位置,那么下标需要进行统一减1

4. 填表顺序 

    

本题的填表顺序是:从左往右,三个表同时填(因为填写原数组第一个节点的值是需要另外两个数组虚拟节点的值)

5. 返回值 :题目要求 + 状态表示    

    

本题的返回值是:min(dp[n][0], min(dp[n][1], dp[n][2]))


4. 代码 

动态规划的固定四步骤:1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();//1.  创建一个规模(n+1*3)的dp表vector<vector<int>>dp(n + 1, vector<int>(3));//n+1:多加了一个虚拟节点//2. 初始化为0,vector默认为0//3. 填表(填表方法:状态转移方程)for (int i = 1; i <= n; i++){//下标都-1是因为数组前面加了一个虚拟节点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];}//4. 确定返回值return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};


完结撒花~

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

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

相关文章

RPA是什么,RPA有什么作用?

在数字化转型的时代背景下&#xff0c;企业面临着提高效率、降低成本和优化流程的巨大压力。RPA作为一种革新性的数字化技术&#xff0c;迅速成为企业实现这些目标的利器。那么&#xff0c;RPA究竟是什么&#xff1f;它又能为企业带来哪些实际作用呢&#xff1f;本文金智维将对…

RAG(检索增强生成)的实现流程;RAG怎么实现检索增强的

目录 RAG(检索增强生成)的实现流程 两次使用大模型:可以不同 一、数据准备阶段 二、应用阶段 RAG怎么实现检索增强的 实现方式 具体举例 RAG(检索增强生成)的实现流程 两次使用大模型:可以不同

【ddnsgo+ipv6】

ddnsgoipv6 DNS解析添加记录ddnsgo配置 DNS解析添加记录 ddnsgo配置

【手撕排序2】快速排序

&#x1f343; 如果觉得本系列文章内容还不错&#xff0c;欢迎订阅&#x1f6a9; &#x1f38a;个人主页:小编的个人主页 &#x1f380; &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 ✌️ &#x1f91e; &#x1f91f; &#x1f918; &#x1f919; &#x1f448; &…

Stable Diffusion的解读(一)

Stable Diffusion的解读&#xff08;一&#xff09; 文章目录 Stable Diffusion的解读&#xff08;一&#xff09;摘要Abstract一、机器学习部分1. Stable Diffusion的早期工作1.1 从编码器谈起1.2 第一条路线&#xff1a;VAE和DDPM1.3 第二条路线&#xff1a;VQVAE1.4 路线的交…

2024年该了解的常用渲染工具

随着图形技术和计算机科学的飞速发展&#xff0c;渲染工具在多个领域中的应用越来越广泛&#xff0c;包括影视特效、建筑设计、工业设计、游戏开发等。了解并掌握一些常用的渲染工具对于设计师和艺术家来说至关重要。 一、效果图建模及渲染软件 Autodesk 3ds Max 拥有强大的建…

解决 “Error: listen EACCES: permission denied 0.0.0.0:80“ 错误

前言 在开发过程中&#xff0c;我们经常会遇到各种各样的错误。其中一个常见的错误是 Error: listen EACCES: permission denied 0.0.0.0:80。这个错误通常发生在尝试启动一个开发服务器时&#xff0c;服务器试图绑定到80端口&#xff0c;但由于权限不足而失败。本文将详细介绍…

flink 内存配置(一):设置Flink进程内存

flink 内存配置&#xff08;一&#xff09;&#xff1a;设置Flink进程内存 flink 内存配置&#xff08;二&#xff09;&#xff1a;设置TaskManager内存 flink 内存配置&#xff08;三&#xff09;&#xff1a;设置JobManager内存 flink 内存配置&#xff08;四&#xff09;…

51c嵌入式~电路~合集14

我自己的原文哦~ https://blog.51cto.com/whaosoft/12443598 一、嵌入式开发中的滤波器设计 什么是滤波器&#xff1f; 各种传感器信号多多少少会携带一些噪声信号&#xff0c;那么通过滤波器就能够更好的降低和去除噪声&#xff0c;还原真实有用信号。 滤波器是一个电路&…

安卓图片的着色教程(tint的使用)

目录 基础夯实&#xff1a;一、Tint的定义与作用二、Tint的应用场景三、Tint的使用方法四、Tint的优势五、注意事项 使用教程&#xff1a;一、xml文件中使用tint效果展示完整代码 二、代码中使用tint效果展示完整代码 三、使图片的主题和背景反色效果展示完整代码 四、运行例程…

Vulnhub靶机——DC-4

#环境准备 dc-4靶机&#xff1a;网卡nat模式 192.168.200.144 kali攻击机&#xff1a;网卡nat模式 192.168.200.129 #渗透过程 #信息收集 老规矩&#xff0c;先用nmap看看有什么端口可以搞 还是一如既往的80和22 访问80端口是一个登录界面&#xff0c;一上来就让我进行爆…

以太网交换安全:MAC地址漂移

一、什么是MAC地址漂移&#xff1f; MAC地址漂移是指设备上一个VLAN内有两个端口学习到同一个MAC地址&#xff0c;后学习到的MAC地址表项覆盖原MAC地址表项的现象。 MAC地址漂移的定义与现象 基本定义&#xff1a;MAC地址漂移发生在一个VLAN内的两个不同端口学习到相同的MAC地…

.NET6中WPF项目添加System.Windows.Forms引用

.NET6中WPF项目添加System.Windows.Forms引用 .NET6的WPF自定义控件默认是不支持System.Windows.Forms引用的&#xff0c;需要添加这个引用方法如下&#xff1a; 1. 在项目浏览器中找到项目右击&#xff0c;选择编辑项目文件&#xff08;Edit Project File&#xff09;。 …

Docker安装XXL-JOB分布式调度任务

一、持久化 1、下载 xxl-job 源码,找到持久化脚本 2、创建 xxl-job 数据库,将上述文件中的脚本在本库执行即可 create database xxl_job charset utf8mb4 collate utf8mb4_general_ci; 二、安装 1、下载 xxl-job 镜像 docker pull xuxueli/xxl-job-admin:2.4.1 2、创建挂…

Kafka 源码 KRaft 模式本地运行

KRaft&#xff08;Kafka Raft Metadata mode&#xff09;&#xff0c;从版本 2.8.0 开始作为测试特性引入&#xff0c;并在后续版本中持续得到改进和增强。 KRaft 模式是指 Kafka 使用 Raft 协议来管理集群元数据的一种运行模式&#xff0c;这标志着 Kafka 向去除对 ZooKeeper …

杨辉三角,洗牌算法

杨辉三角 给定一个非负整数numRows&#xff0c;生成杨辉三角的前numRows行。 在杨辉三角中&#xff0c;每个数是它的左上方和右上方的数的和。 public List<List<Integer>> generate(int numRows){List<List<Integer>> ret new ArrayList<>();…

计算机网络——HTTP篇

基础篇 IOS七层网络模型 TCP/IP四层模型&#xff1f; 应⽤层&#xff1a;位于传输层之上&#xff0c;主要提供两个终端设备上的应⽤程序之间的通信&#xff0c;它定义了信息交换的格式&#xff0c;消息会交给下⼀层传输层来传输。 传输层的主要任务就是负责向两台设备进程之间…

基于SpringBoot的Java教学支持系统开发指南

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理教学辅助平台的相关信息成为必然。开发合适…

MySQL:表的增删改查(进阶)

表的增删改查&#xff08;进阶&#xff09;十分重要&#xff0c;也较有难度&#xff0c;需多花时间掌握。 一、NULL约束&#xff1a; 在加null约束之前&#xff0c;id可以插入null&#xff0c;在加上null约束之后&#xff0c;id不再可以插入null。 二、unique约束&#xff1a;…

Latex中给公式加边框

1、这里使用的不是 amsmath 的 \boxed 命令, 而是 empheq 的 empheq 环境以及 xcolor 的 \fcolorbox 命令, 下面是代码, 可以分别阅读这两个手册来获取更多的信息 \documentclass{article} \usepackage{xcolor} \usepackage{empheq} \usepackage{amsmath} \begin{document}\be…