[Algorithm][动态规划][简单多状态DP问题][按摩师][打家劫舍Ⅱ][删除并获得点数][粉刷房子]详细讲解

目录

  • 1.按摩师
    • 1.题目链接
    • 2.算法思路详解
    • 3.代码实现
  • 2.打家劫舍 II
    • 1.题目链接
    • 2.算法思路详解
    • 3.代码实现
  • 3.删除并获得点数
    • 1.题目链接
    • 2.算法思路详解
    • 3.代码实现
  • 4.粉刷房子
    • 1.题目链接
    • 2.算法思路详解
    • 3.代码实现


1.按摩师

1.题目链接

  • 按摩师

2.算法思路详解

  • 思路
    • 确定状态表示 -> dp[i]的含义

      • 选择到i位置的时候,此时的最长预约时长
      • 本题,状态表示还可以继续细分:
        • f[i]:选择到i位置的时候,nums[i]必选,此时的最长预约时长
        • g[i]:选择到i位置的时候,nums[i]不选,此时的最长预约时长
    • 推导状态转移方程

      • f[i] = g[i - 1] + nums[i]
      • g[i] = max(f[i - 1], g[i - 1])
        请添加图片描述
    • 初始化:f[0] = nums[0], g[0] = 0

    • 确定填表顺序:从左往右,两个表一起填

    • 确定返回值:max(f[n - 1], g[n - 1])


3.代码实现

int massage(vector<int>& nums) 
{int n = nums.size();if(n == 0) return 0;vector<int> f(n);vector<int> g(n);f[0] = nums[0];for(int i = 1; i < n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);
}

2.打家劫舍 II

1.题目链接

  • 打家劫舍 II

2.算法思路详解

  • 思路解析:本题比打家劫舍Ⅰ只多了环形问题,那么只需将环形问题分类讨论(依据nums[0]),拆解为两个线性的打家劫舍Ⅰ问题即可
    • 第一个位置偷nums[0] + _rob[2, n - 2] <— 第二个位置和最后一个位置不偷
    • 第一个位置不偷_rob(1, n - 1) <— 偷第二个位置和最后一个位置
  • 思路
    • 确定状态表示 -> dp[i]的含义

      • i位置的时候,此时的最大金额
      • 本题,状态表示还可以继续细分:
        • f[i]:偷到i位置的时候,nums[i]必偷,此时的最大金额
        • g[i]:偷到i位置的时候,nums[i]不偷,此时的最大金额
    • 推导状态转移方程

      • f[i] = g[i - 1] + nums[i]
      • g[i] = max(f[i - 1], g[i - 1])
        请添加图片描述
    • 初始化:f[0] = nums[0], g[0] = 0

    • 确定填表顺序:从左往右,两个表一起填

    • 确定返回值:max(f[n - 1], g[n - 1])


3.代码实现

class Solution
{
public:int rob(vector<int>& nums) {int n = nums.size();// 分类讨论,取两种情况中的最大值return max(nums[0] + _rob(nums, 2, n - 2), _rob(nums, 1, n - 1));}int _rob(vector<int>& nums, int left, int right){if(left > right) return 0;int n = nums.size();vector<int> f(n); // 选vector<int> g(n); // 不选f[left] = nums[left];for(int i = left + 1; i <= right; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[right], g[right]);}
};

3.删除并获得点数

1.题目链接

  • 删除并获得点数

2.算法思路详解

  • 思路解析:本题可以先做一个预处理,将问题转化为打家劫舍

    • 思路
      • 打家劫舍要求访问数组中的数的顺序是连续的,但本题原始数组显然不符合要求
      • 虽然原始数组数值不符合要求,但是经过转换,数组下标是可以符合顺序连续的
    • 做法
      • 将原始数组中的数,统计到arr,然后在arr中,做一次打家劫舍问题即可
      • 此时,数值相同的值的和可以被其本身值作为arr的下标索引到 <— hash[x] = sum(x)
      • arr[i]i这个数出现的总和
        请添加图片描述
  • 思路

    • 确定状态表示 -> dp[i]的含义

      • i位置的时候,此时获得的最大点数
      • 本题,状态表示还可以继续细分:
        • f[i]:选到i位置的时候,nums[i]必选,此时获得的最大点数
        • g[i]:选到i位置的时候,nums[i]不选,此时获得的最大点数
    • 推导状态转移方程

      • f[i] = g[i - 1] + arr[i]
      • g[i] = max(f[i - 1], g[i - 1])
        请添加图片描述
    • 初始化:f[0] = arr[0], g[0] = 0

    • 确定填表顺序:从左往右,两个表一起填

    • 确定返回值:max(f[n], g[n])


3.代码实现

int deleteAndEarn(vector<int>& nums) 
{sort(nums.begin(), nums.end());int n = nums.back(); // maxvector<int> arr(n + 1);for(auto& x : nums){arr[x] += x;}vector<int> f(n + 1);vector<int> g(n + 1);for(int i = 1; i <= n; i++){f[i] = g[i - 1] + arr[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n], g[n]);
}

4.粉刷房子

1.题目链接

  • 粉刷房子

2.算法思路详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义:i -> 到了哪个位置,j -> 这个位置的哪个颜色

      • 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]
        请添加图片描述
    • 初始化:dp[0][0] = dp[0][1] = dp[0][2] = 0

    • 确定填表顺序:从左往右,一次填写三个表

    • 确定返回值:min(dp[n][0], min(dp[n][1], dp[n][2]))


3.代码实现

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]));
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Mac | Mac 移动硬盘无法分区问题

现象问题 电脑配置&#xff1a;MacBook Pro M1&#xff0c;系统 Sonoma Mac 系统新升级了 Sonoma&#xff0c;结果出现各种问题。外接屏幕居然不能旋转 90 &#xff0c;查了一下是Sonoma系统导致的&#xff0c;以及莫名发热的问题。想着要么回退一下系统算了&#xff0c;于是网…

ICQ 将于 6 月关闭,这是一种奇怪的方式,发现它在 2024 年仍然活跃

你知道ICQ还活着吗&#xff1f;不过&#xff0c;不要太兴奋;它将永远消失。 还记得ICQ吗&#xff1f;如果你这样做了&#xff0c;你可能会记得它是AOL在1998年购买的Messenger客户端&#xff0c;就在Yahoo Instant Messager和MSN Messenger加入竞争的时候。然后Skype出现了&…

Linux--线程的认识(一)

线程的概念 线程&#xff08;Thread&#xff09;是操作系统中进行程序执行的最小单位&#xff0c;也是程序调度和分派的基本单位。它通常被包含在进程之中&#xff0c;是进程中的实际运作单位。一个线程指的是进程中一个单一顺序的控制流&#xff0c;一个进程中可以并发多个线…

Redis内存回收-内存淘汰策略

LFU的访问次数之所以叫做逻辑访问次数&#xff0c;是因为并不是每次key被访问都计数&#xff0c;而是通过运算&#xff1a; 生成0~1之间的随机数R计算 (旧次数 * lfu_log_factor 1)&#xff0c;记录为P如果 R < P &#xff0c;则计数器 1&#xff0c;且最大不超过255访问…

【电路笔记】-二阶滤波器

二阶滤波器 二阶(或双极)滤波器由两个连接在一起的 RC 滤波器部分组成,可提供 -40dB/十倍频程滚降率。 1、概述 二阶滤波器也称为 VCVS 滤波器,因为运算放大器用作压控电压源放大器,是有源滤波器设计的另一种重要类型,因为与我们之前研究过的有源一阶 RC 滤波器一起,…

C++中的指针——指针所占内存空间

提问&#xff1a;指针也是一种数据类型&#xff0c;那么这种数据类型占用多少内存空间呢&#xff1f; 示例 运行结果 示例 运行结果

【引领光子学革命:机器学习与深度学习重塑设计与应用新纪元】

光子器件的逆向设计&#xff1a;利用深度学习技术&#xff0c;可以优化多参数光子器件的设计。通过大量的数据分析和模式识别&#xff0c;深度学习算法能够预测和优化光子器件的性能&#xff0c;从而缩短设计周期并降低设计成本。 超构表面与超材料设计&#xff1a;在新型光学材…

智源联合多家机构推出自动化多样性信息检索评测基准AIR-Bench

智源研究院联合Jina AI、Zilliz、HuggingFace、中国科技大学、中国人民大学、北京邮电大学等多家机构联合推出专门针对检索任务和RAG场景的评测AIR-Bench。AIR-Bench首次提出在检索评测任务中使用LLMs生产评估数据&#xff0c;避免模型过拟合测试数据。同时&#xff0c;由于使用…

【InternLM实战营第二期笔记】01:书生浦语大模型全链路开源体系+InternLM2技术报告

文章目录 课程笔记InternLM2 在数据处理上的进步2.0 版本的主要 features从模型到应用评测 InternLM2 技术报告 阅读笔记Infra训练框架&#xff1a;InternEvo模型架构 预训练数据文本代码长上下文 预训练设置Tokenization预训练超参数 预训练阶段 AlignmentCOOL RL长上下文微调…

Linux连接主机xshell,Linux vi编辑器使用教程

Linux连接主机xshell Linux vi编辑器使用教程 以下是Linux中vi编辑器的使用教程&#xff1a; 打开终端并输入vi命令&#xff0c;然后按回车键打开vi编辑器。 默认情况下&#xff0c;vi编辑器处于命令模式。在命令模式下&#xff0c;你可以执行一些编辑操作。例如&#xff1a…

从0开始学统计-t检验

1.什么是t检验&#xff1f; t检验是一种用于比较两个样本均值之间差异是否显著的统计方法。它通常用于以下几种情况&#xff1a; &#xff08;1&#xff09;单样本 t 检验&#xff1a;用于检验一个样本的平均值是否与一个已知的总体平均值&#xff08;或者一个假设的总体平均…

SpringCache+redis实现缓存

SpringCacheredis实现缓存 介绍注解入门程序环境准备1). 数据库准备2). 导入基础工程3). 注入CacheManager4). 引导类上加EnableCachingCachePut注解1). 在save方法上加注解CachePut2). 测试 CacheEvict注解1). 在 delete 方法上加注解CacheEvict2). 测试3). 在 update 方法上加…

# 文件或目录损坏且无法读取 的解决方案

文件或目录损坏且无法读取 的解决方案 一、问题描述&#xff1a; windows 系统下&#xff0c;当对某一个文件或文件夹操作时&#xff0c;出现【文件或目录损坏且无法读取】&#xff0c;这时不管对其进行修改、删除、更改属性等操作&#xff0c;都不能正常进行&#xff0c;在 …

揭秘《庆余年算法番外篇》:范闲如何使用维吉尼亚密码解密二皇子密信

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容&#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣&#xff01; 推荐&#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航&#xff1a; LeetCode解锁100…

高斯过程学习笔记

目录 基础知识 例子 推荐 A Visual Exploration of Gaussian Processes (distill.pub) AB - Introduction to Gaussian Processes - Part I (bridg.land) 基础知识 高斯过程回归&#xff08;Gaussian Process Regression&#xff09; - 知乎 (zhihu.com) 高斯过程&#x…

Linux自动重启系统脚本测试工具

前言 脚本允许用户指定重启的次数和重启间隔时间&#xff0c;并自动生成相应的定时任务。通过使用这个脚本&#xff0c;系统管理员可以轻松地设置重启测试。每次重启操作都会被记录下来&#xff0c;以便用户随时了解测试情况。 一、脚本 #!/bin/bashif [ "$1" &qu…

CAD二次开发(4)-编辑图形

工具类&#xff1a;EditEntityTool.cs using Autodesk.AutoCAD.ApplicationServices; using Autodesk.AutoCAD.DatabaseServices; using Autodesk.AutoCAD.Geometry; using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Th…

20道经典自动化测试面试题

概述 觉得自动化测试很难&#xff1f; 是的&#xff0c;它确实不简单。但是学会它&#xff0c;工资高啊&#xff01; 担心面试的时候被问到自动化测试&#xff1f; 嗯&#xff0c;你担心的没错&#xff01;确实会被经常问到&#xff01; 现在应聘软件测试工程师的岗位&…

神经网络不确定性综述(Part V)——Uncertainty measures and quality

相关链接&#xff1a; 神经网络不确定性综述(Part I)——A survey of uncertainty in deep neural networks-CSDN博客 神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods-CSDN博客 神经网络不确定性综述(Part III)——Uncertainty est…

基于深度学习和去卷积的盲源分离方法在旋转机械上的应用

关键词&#xff1a;预测性维护、盲源分离、振动分析、传递函数移除、二阶循环平稳性、轴承监测、机器学习 振动是旋转机械中主要的故障指示器&#xff0c;它们主要来源于两个方面&#xff1a;一个是与齿轮相关的振动&#xff08;主要源于齿轮啮合过程中的冲击和不平衡负载&…
最新文章