C++算法第十二天

本篇文章,我们继续学习动态规划

第一题

题目链接

面试题 17.16. 按摩师 - 力扣(LeetCode)

题目解析

代码原理

代码编写

细节问题处理

这里的细节问题就是当n == 0时的这种情况

完整源代码

class Solution {

public:

    int massage(vector<int>& nums) {

        int n = nums.size();

        //细节处理

        if(n == 0)

        return n;

        //建表

        vector<int> f(n), g(n);

        //初始化

        f[0] = nums[0], g[0] = 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(g[n - 1], f[n - 1]);

    }

};

第二题

题目链接

213. 打家劫舍 II - 力扣(LeetCode)

题目解析

代码原理

代码编写

class Solution {

public:

    int sloutionway(vector<int>& nums,int left,int right)

    {

        if(left > right) return 0;

        int n = nums.size();

        //建表

        vector<int>f(n),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]);

    }

    int rob(vector<int>& nums) {

        int n = nums.size();

        return max(sloutionway(nums, 1, n - 1), nums[0] + sloutionway(nums, 2, n - 2));

    }

};

第三题

题目链接

740. 删除并获得点数 - 力扣(LeetCode)

题目解析

下面的示例二也是一样的道理,总结一下还是选和不选的问题,只不过只有第一次删除才获得点数,后面删除的cur[i] + 1和cur[i] - 1都不加点数

代码原理

代码编写

class Solution {

public:

    int deleteAndEarn(vector<int>& nums) {

        const int N = 10001;

        //数组预处理

        int arr[N] = {0};

        for(auto cur: nums) arr[cur] += cur;

        //建表

        vector<int> f(N),g(N);

        //初始化

        f[0] = arr[0];

        //填表

        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 - 1], g[N - 1]);

    }

};

本题总结

遇到与《选和不选》相关且数字有序(无序)有可能还是数字不连续的,需要先预处理一下原先的数组,之后在预处理好的新数组里面进行一次打家劫舍问题即可。

本篇文章的内容就先到这里,我们下期文章再见。

记得一键三联哦!!!

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

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

相关文章

java全栈day20--Web后端实战(Mybatis基础2)

一、Mybatis基础 1.1辅助配置 配置 SQL 提示。 默认在 mybatis 中编写 SQL 语句是不识别的。可以做如下配置&#xff1a; 现在就有sql提示了 新的问题 产生原因&#xff1a; Idea 和数据库没有建立连接&#xff0c;不识别表信息 解决方式&#xff1a;在 Idea 中配置 MySQL 数…

2023年厦门市第30届小学生C++信息学竞赛复赛上机操作题(三、2023C. 太空旅行(travel))

#include <bits/stdc.h>using namespace std;struct Ship {int u; // 从地球到火星的时间int v; // 从火星到天王星的时间 };// 自定义比较函数 bool cmp(const Ship &a, const Ship &b) {return a.u max(a.v, b.u) b.v < b.u max(b.v, a.u) a.v; }int ma…

使用qemu搭建armv7嵌入式开发环境

目录 目录 1 概述 2 环境准备 2.1 vexpress系列开发板介绍 2.2 安装工具 2.2.1 安装交叉工具链 2.2.2 安装qemu 2.2.3 安装其他工具 3 启动uboot 3.1 uboot下载与编译 3.1.1 下载 3.1.2 编译 3.2 使用qemu启动uboot 4 启动kernel 4.1 下载和编译kernel 4.1.1 下…

CSDN外链失效3:

参考我之前的博客&#xff1a; 外链失效博客1&#xff1a;随想笔记1&#xff1a;CSDN写博客经常崩溃&#xff0c;遇到外链图片转存失败怎么办_csdn外链图片转存失败-CSDN博客 外链失效博客2&#xff1a;网络随想2&#xff1a;转语雀_md格式转语雀lake格式-CSDN博客 markdown…

《LangChain大模型应用开发》书籍分享

前言 ChatGPT和OpenAI开发的GPT模型不仅改变了我们的写作和研究方式&#xff0c;还改变了我们处理信息的方式。《LangChain大模型应用开发》讨论了聊天模式下的LLM的运作、能力和局限性&#xff0c;包括ChatGPT和Gemini。书中通过一系列实际例子演示了如何使用LangChain框架构…

Jenkins持续集成部署——jenkins安装

前言 Jenkins 是一个开源的自动化服务器&#xff0c;主要用于持续集成&#xff08;CI&#xff09;和持续交付&#xff08;CD&#xff09;。它为软件开发团队提供了一个易于使用的平台来自动化构建、测试和部署应用程序的过程。 Jenkins 主要功能 1. 持续集成 (CI) 自动构建…

飞牛 fnos 使用docker部署 bili-sync:打造自动化 B 站资源下载器,与主流媒体服务器无缝衔接

Bili-Sync介绍及相关部署操作 一、Bili-Sync概述 Bili-Sync是哔哩哔哩内容同步助手&#xff0c;它能借助用户提供的登录信息&#xff0c;定期对用户的视频合集以及个人收藏进行遍历&#xff0c;找出还没在本地保存的新内容&#xff0c;然后自动下载到本地存储&#xff0c;以此…

Idean 处理一个项目引用另外一个项目jar 但jar版本低的问题

当在idea中一个module A引用另外一个项目B的jar&#xff0c;但是从私服仓库中拉下的jar版本比较低导致编译不通过时&#xff0c;可以把项目B拉下来&#xff0c;重新编译打包jar跟新到本地的仓库 选中右边菜单的Maven 选中对应的项目B-》Lifecycle->双击 install也可以按住c…

【day11】面向对象编程进阶(继承)

概述 本文深入探讨面向对象编程的核心概念&#xff0c;包括继承、方法重写、this和super关键字的使用&#xff0c;以及抽象类和方法的定义与实现。通过本文的学习&#xff0c;你将能够&#xff1a; 理解继承的优势。掌握继承的使用方法。了解继承后成员变量和成员方法的访问特…

高效准确的PDF解析工具,赋能企业非结构化数据治理

目录 准确性高&#xff1a;还原复杂版面元素 使用便捷&#xff1a;灵活适配场景 贴心服务&#xff1a;快速响应机制 在数据为王的时代浪潮中&#xff0c;企业数据治理已成为组织优化运营、提高竞争力的关键。随着数字化进程的加速&#xff0c;企业所积累的数据量呈爆炸式增长…

Unity全局雾效

1、全局雾效是什么 全局雾效&#xff08;Global Fog&#xff09;是一种视觉效果&#xff0c;用于在3D场景中模拟大气中的雾气对远处物体的遮挡 它通过在场景中加入雾的效果&#xff0c;使得距离摄像机较远的物体看起来逐渐被雾气覆盖&#xff0c;从而创造出一种朦胧、模糊的视…

解决Apache/2.4.39 (Win64) PHP/7.2.18 Server at localhost Port 80问题

配置一下apache里面的配置文件&#xff1a;httpd.conf 和 httpd.vhosts.conf httpd.conf httpd-vhosts.conf 重启服务 展示&#xff1a; 浏览器中中文乱码问题&#xff1a;

【Spring事务】深入浅出Spring事务从原理到源码

什么是事务 保证业务操作完整性的一种数据库机制 &#xff08;driver 驱动&#xff09;事务特定 ACID A 原子性 &#xff08;多次操作 要不一起成功 要不一起失败 &#xff08;部分失败 savepoint&#xff09;&#xff09; C 一致性 &#xff08;事务开始时数据状态&#xff0c…

MFC/C++学习系列之简单记录13

MFC/C学习系列之简单记录13 前言memsetList Control代码注意 总结 前言 今天记录一下memset和List control 的使用吧&#xff01; memset memset通常在初始化变量或清空内存区域的时候使用&#xff0c;可以对变量设定特定的值。 使用&#xff1a; 头文件&#xff1a; C&#…

C# cad启动自动加载启动插件、类库编译 多个dll合并为一个

可以通过引用costura.fody的包&#xff0c;编译后直接变为一个dll 自动加载写入注册表、激活码功能: 【CAD二次开发教程-实例18-启动加载与自动运行-哔哩哔哩】 https://b23.tv/lKnki3f https://gitee.com/zhuhao1912/cad-atuo-register-and-active

Android Studio AI助手---Gemini

从金丝雀频道下载最新版 Android Studio&#xff0c;以利用所有这些新功能&#xff0c;并继续阅读以了解新增内容。 Gemini 现在可以编写、重构和记录 Android 代码 Gemini 不仅仅是提供指导。它可以编辑您的代码&#xff0c;帮助您快速从原型转向实现&#xff0c;实现常见的…

固定电话采用的是模拟信号还是数字信号?如果通话两端采用不同的信号会发生什么?

固定电话信号大揭秘&#xff1a;模拟与数字信号的纠缠 模拟信号 VS 数字信号&#xff1a;谁是电话界的“老江湖”&#xff1f; 固定电话采用的是模拟信号还是数字信号&#xff1f; 这其实取决于接入方式&#xff1a; 铜线接入&#xff1a;传统方式&#xff0c;使用模拟电信号…

<项目代码>YOLO Visdrone航拍目标识别<目标检测>

项目代码下载链接 &#xff1c;项目代码&#xff1e;YOLO Visdrone航拍目标识别&#xff1c;目标检测&#xff1e;https://download.csdn.net/download/qq_53332949/90163918YOLOv8是一种单阶段&#xff08;one-stage&#xff09;检测算法&#xff0c;它将目标检测问题转化为一…

druid与pgsql结合踩坑记

最近项目里面突然出现一个怪问题&#xff0c;数据库是pgsql&#xff0c;jdbc连接池是alibaba开源的druid&#xff0c;idea里面直接启动没问题&#xff0c;打完包放在centos上和windows上cmd窗口都能直接用java -jar命令启动&#xff0c;但是放到国产信创系统上就是报错&#xf…

LabVIEW电机控制中的主动消抖

在LabVIEW电机控制系统中&#xff0c;抖动现象&#xff08;如控制信号波动或机械振动&#xff09;会影响系统的稳定性和精度。通过使用主动消抖算法&#xff0c;可以有效降低抖动&#xff0c;提高控制性能。本文将介绍几种主流的主动消抖算法&#xff0c;并结合具体应用案例进行…