当前位置: 首页 > news >正文

【算法|动态规划No.9】leetcodeLCR 091. 粉刷房子

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
在这里插入图片描述

点击直接跳转到该题目

1️⃣题目描述

假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例1:

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。

示例2:

输入: costs = [[7,6,2]]
输出: 2

注意事项:

  • costs.length == n
  • costs[i].length == 3
  • 1 <= n <= 100
  • 1 <= costs[i][j] <= 20

2️⃣题目解析

这里我们定义一个大小为(n + 1)* 3的二维dp表,之所以是n + 1是为了解决dp表的初始化问题(多出来的那个1我们可以将其理解为一个虚拟节点),具体解释如下:

  • 为什么要使用大小为 (n+1) x 3 的数组呢?这是因为我们希望使用 dp[0] 表示第 0 个房屋(即没有房屋)的情况,而不是从 dp[1] 开始表示第一个房屋的情况。为了方便地处理边界情况,我们可以将数组的大小设置为 (n+1) x 3,从而在 dp[1] ~ dp[n] 中存储每个房屋对应的最小成本,而 dp[0] 可以被初始化为全0。

dp[i][0] 表示涂到第 i 房屋时,将其涂成红颜色的最小成本。
dp[i][1] 表示涂到第 i 房屋时,将其涂成蓝颜色的最小成本。
dp[i][2] 表示涂到第 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]

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][0],dp[i-1][1]) + costs[i-1][2];}return min(dp[n][0],min(dp[n][1],dp[n][2]));}
};

通过啦:
在这里插入图片描述

相关文章:

【算法|动态规划No.9】leetcodeLCR 091. 粉刷房子

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

基于SpringBoot的图书进销存管理系统

目录 前言 一、技术栈 二、系统功能介绍 用户信息管理 图书类型管理 商品退货管理 客户信息管理 图书添加 客户添加 应收金额 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实…...

回归预测 | MATLAB实现PSO-SVR粒子群优化支持向量机回归多输入单输出预测

回归预测 | MATLAB实现PSO-SVR粒子群优化支持向量机回归多输入单输出预测 目录 回归预测 | MATLAB实现PSO-SVR粒子群优化支持向量机回归多输入单输出预测预测效果基本介绍模型描述程序设计预测效果 <...

vue3使用v-model控制子组件进行双向数据绑定

vue2写法: 中父组件调用子组件: <child :isShow.sync"isShow" v-show"isShow"/> 子组件想要消失, 在子组件写: this.$emit("update:isShow",false); 具体代码就不粘贴了 vue3写法: 父组件核心代码: v-model:a"xxx" 子组…...

.netCore .net5,6,7 存日志文件

如果你使用 .netCore及以上版本(.net5,.net6,.net7)... 系统默认自带日志中间件(log4net) 对,就是上次java 日志大漏洞的兄弟....... 控制台自动打印日志就是它的功劳 现在我们想存日志文件,怎么办 很简单. 1.在项目中添加日志配置文件 文件名 : log4net.config 不能…...

【数据结构---排序】很详细的哦

本篇文章介绍数据结构中的几种排序哦~ 文章目录 前言一、排序是什么&#xff1f;二、排序的分类 1.直接插入排序2.希尔排序3.选择排序4.冒泡排序5.快速排序6.归并排序总结 前言 排序在我们的生活当中无处不在&#xff0c;当然&#xff0c;它在计算机程序当中也是一种很重要的操…...

GitHub爬虫项目详解

前言 闲来无事浏览GitHub的时候&#xff0c;看到一个仓库&#xff0c;里边列举了Java的优秀开源项目列表&#xff0c;包括说明、仓库地址等&#xff0c;还是很具有学习意义的。但是大家也知道&#xff0c;国内访问GitHub的时候&#xff0c;经常存在访问超时的问题&#xff0c;…...

辅助驾驶功能开发-功能对标篇(7)-NOA领航辅助系统-上汽荣威

1.横向对标参数 厂商上汽荣威车型荣威RX5(燃油车)上市时间2022Q3方案10V3R摄像头前视摄像头1*(8M)侧视摄像头4后视摄像头1环视摄像头4DMS摄像头1雷达毫米波雷达34D毫米波雷达/超声波雷达12激光雷达/域控供应商1*(宏景智驾)辅助驾驶软件供应商地平线高精度地图中海庭芯片J3合作…...

第0次 序言

突然想起有好多书没有看&#xff0c;或者看了也没留下任何记录&#xff0c;以后有空必须得好好整理才行&#xff0c;这次就从《Linux命令行和shell脚本编程大全开始》 本文完全是闲聊&#xff0c;自娱自乐&#xff0c;我觉得做开发是一件很快乐的事情&#xff0c;但是工作是开发…...

ESP32设备驱动-OLED显示单个或多个DS18B20传感器数据

OLED显示单个或多个DS18B20传感器数据 文章目录 OLED显示单个或多个DS18B20传感器数据1、DS18B20介绍2、硬件准备3、软件准备4、代码实现4.1 读取单个DS18B20数据4.2 驱动多个DS18B20传感器4.3 OLED显示DS18B20数据在本文中,我们将介绍如何ESP32驱动单个或多个DS18B20传感器,…...

MongoDB快速上手

文章目录 1、mongodb相关概念1.1、业务应用场景1.2、MongoDB简介1.3、体系结构1.3.1 数据库 (databases) 管理语法1.3.2 集合 (collection) 管理语法 1.4、数据模型1.5、MongoDB的特点 2、单机部署3、基本常用命令3.1、案例需求3.2、数据库操作3.2.1 选择和创建数据库3.2.2 数据…...

maven 初学

1. maven 安装 配置安装 路径 maven 下载位置: D:\software\apache-maven-3.8.6 默认仓库位置: C:\Users\star-dream\.m2\repository 【已更改】 本地仓库设置为&#xff1a;D:\software\apache-maven-3.8.6\.m2\repository 镜像已更改为阿里云中央镜像仓库 <mirrors>…...

解决WPF+Avalonia在openKylin系统下默认字体问题

一、openKylin简介 openKylin&#xff08;开放麒麟&#xff09; 社区是在开源、自愿、平等和协作的基础上&#xff0c;由基础软硬件企业、非营利性组织、社团组织、高等院校、科研机构和个人开发者共同创立的一个开源社区&#xff0c;致力于通过开源、开放的社区合作&#xff…...

智能合约漏洞,Dyna 事件分析

智能合约漏洞&#xff0c;Dyna 事件分析 1. 漏洞简介 https://twitter.com/BlockSecTeam/status/1628319536117153794 https://twitter.com/BeosinAlert/status/1628301635834486784 2. 相关地址或交易 攻击交易 1&#xff1a; https://bscscan.com/tx/0x7fa89d869fd1b89e…...

Elasticsearch基础篇(四):Elasticsearch7.x的官方文档学习(Set up Elasticsearch)

Set up Elasticsearch 1 Configuring Elasticsearch(配置 Elasticsearch)1.1 Setting JVM Options(设置JVM选项)1.2 Secure Settings(安全设置)Introduction(介绍)Using the Keystore(使用密钥库)Applying Changes(应用更改)Reloadable Secure Settings(可重新加载的安全设置)R…...

二叉树的遍历方式和代码

二叉树的三种遍历和代码 1.前序遍历2.中序遍历3.后序遍历4.三种遍历方式的代码实现 1.前序遍历 学习二叉树结构&#xff0c;最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线&#xff0c;依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具…...

小样本学习——匹配网络

目录 匹配网络 &#xff08;1&#xff09;简单介绍&#xff1a; &#xff08;2&#xff09;专业术语 &#xff08;3&#xff09;主要思想 &#xff08;4&#xff09;训练过程 问题 回答 MANN 匹配网络 &#xff08;1&#xff09;简单介绍&#xff1a; Matching netwo…...

CSS 常用样式 之字体属性

font-weight&#xff08;字体粗细&#xff09; 字体粗细用于设置文本的粗细程度&#xff0c;可以使用如下的值&#xff1a; normal&#xff1a;正常字体&#xff08;默认&#xff09;bold&#xff1a;加粗字体bolder&#xff1a;更加加粗lighter&#xff1a;更加细 代码实例…...

nodejs+vue游戏测评交流系统elementui

可以实现首页、发布招募、公司资讯、我的等&#xff0c;另一方面来说也可以提高在游戏测评交流方面的效率给相关管理人员的工作带来一定的便利。在我的页面可以对游戏攻略、我的收藏管理、实际上如今信息化成为一个未来的趋势或者可以说在当前现代化的城市典范中,发布招募等功能…...

1.2.OpenCV技能树--第一单元--OpenCV安装

目录 1.文章内容来源 2.OpenCV安装 3.课后习题代码复现 4.易错点总结与反思 1.文章内容来源 1.题目来源:https://edu.csdn.net/skill/opencv/opencv-662dbd65c89d4ddb9e392f44ffe16e1a?category657 2.资料来源:https://edu.csdn.net/skill/opencv/opencv-662dbd65c89d4ddb…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...