【算法-动态规划】打家劫舍专题
文章目录
- 1.打家劫舍
- 1.1一维数组
- 1.2三变量法
- 1.3双数组法
- 2.打家劫舍2
- 2.1双数组法
- 2.2 三变量法
- 3.打家劫舍3
- 3.1动态规划
- 3.2双变量法
- 4.删除相邻数字的最大分数
- 4.1双状态数组
- 4.2一维数组
- 4.3三变量法
1.打家劫舍
198. 打家劫舍 - 力扣(LeetCode)
1.1一维数组
class Solution
{
public:int rob(vector<int> &nums){int n = nums.size();if (n == 0)return 0;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额vector<int> dp(n, 0);dp[0] = nums[0];if (n == 1)return dp[0];dp[1] = max(nums[0], nums[1]);if (n == 2)return dp[1];for (int k = 2; k <= n - 1; k++){dp[k] = max(dp[k - 1], nums[k] + dp[k - 2]);}return dp[n - 1];}
};
1.2三变量法
class Solution
{
public:int rob(vector<int> &nums){int n = nums.size();if (n == 0)return 0;int prv = nums[0]; // dp[0]if (n == 1)return prv;int cur = max(nums[0], nums[1]); // dp[1]if (n == 2)return cur;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额for (int i = 2; i < n; i++){// dp[k] = max(dp[k - 1], nums[k] + dp[k - 2]);int tmp = max(cur, nums[i] + prv);prv = cur;cur = tmp;}return cur;}
};
1.3双数组法
class Solution
{
public:int massage(vector<int> &nums){int n = nums.size();if (n == 0)return 0;// f[i] 走到i时 偷nums[i]// g[i] 走到i时 不偷nums[i]vector<int> f(n);vector<int> g(n); // auto g = f;f[0] = nums[0];for (int i = 1; i < n; i++){f[i] = nums[i] + g[i - 1];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};
2.打家劫舍2
打家劫舍2
2.1双数组法
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}int rob1(vector<int>& nums, int left, int right) {if (left > right)return 0;int n = nums.size();vector<int> f(n);auto g = f;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]);}
};
2.2 三变量法
class Solution
{
public:int robRange(vector<int> &nums, int start, int end){int n = end - start + 1;if (n == 0)return 0;int prv = nums[start]; // dp[k-2]if (n == 1)return prv;int cur = max(nums[start], nums[start + 1]); // dp[k-1]if (n == 2)return cur;for (int i = start + 2; i <= end; i++){// dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2]);int tmp = max(cur, nums[i] + prv);prv = cur;cur = tmp;}return cur;}int rob(vector<int> &nums){int n = nums.size();if (n == 1)return nums[0];else if (n == 2)return max(nums[0], nums[1]);else if (n == 3)return max(max(nums[0], nums[1]), nums[2]);// 偷nums[0]不能偷nums[1]和nums[n-1] 能偷[2, n - 2]// 不偷nums[0] 能偷[1, n - 1]return max(nums[0] + robRange(nums, 2, n - 2), robRange(nums, 1, n - 1));}
};
3.打家劫舍3
3.1动态规划
class Solution
{
public:unordered_map<TreeNode *, int> is, no;void dfs(TreeNode *node){if (node == nullptr)return;dfs(node->left);dfs(node->right);is[node] = node->val + no[node->left] + no[node->right];no[node] = max(is[node->left], no[node->left]) + max(is[node->right], no[node->right]);}int rob(TreeNode *root){dfs(root);return max(is[root], no[root]);}
};
3.2双变量法
struct SubtreeStatus
{int is;int no;
};class Solution
{
public:SubtreeStatus dfs(TreeNode *node){if (node == nullptr)return {0, 0};auto left = dfs(node->left);auto right = dfs(node->right);int selected = node->val + left.no + right.no;int notSelected = max(left.is, left.no) + max(right.is, right.no);return {selected, notSelected};}int rob(TreeNode *root){auto rootStatus = dfs(root);return max(rootStatus.is, rootStatus.no);}
};
4.删除相邻数字的最大分数
删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com)

- 一个数组选了x可以得x分 但是值为x-1和x+1的数将会消失 直到数字全被消失或选择 问最高分数
- 遍历数组arr 填充hash arr中的per在hash中作下标 表示 【谁 出现的总和】如4在arr中出现了2次 则hash[4]=8
- 由此问题转变为 在hash中 我“偷”了某个下标i 获得了hash[i]分数 与i相邻的就不能偷了
4.1双状态数组
#include <iostream>
#include <vector>
using namespace std;int main()
{const int N = 1e4 + 10;int hash[N] = {0};int n = 0;cin >> n;int per = 0;int end = 0;for (int i = 0; i < n; i++){cin >> per;end = per > end ? per : end;hash[per] += per;}vector<int> f(end + 1, 0);vector<int> g(end + 1, 0);for (int i = 1; i <= end; i++){f[i] = g[i - 1] + hash[i];g[i] = max(f[i - 1], g[i - 1]);}cout << max(f[end], g[end]) << endl;return 0;
}
4.2一维数组
#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;int per = 0;int end = 0;const int N = 1e4 + 10;int hash[N] = {0};for (int i = 0; i < n; i++){cin >> per;end = per > end ? per : end;hash[per] += per;}vector<int> dp(end + 1, 0);// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额dp[0] = hash[0];dp[1] = max(hash[0], hash[1]);for (int k = 2; k <= end; k++){dp[k] = max(dp[k - 1], hash[k] + dp[k - 2]);}cout << dp[end] << endl;return 0;
}
4.3三变量法
#include <iostream>
#include <vector>
using namespace std;int main()
{const int N = 1e4 + 10;int hash[N] = {0};int n = 0;cin >> n;int per = 0;int end = 0;for (int i = 0; i < n; i++){cin >> per;end = per > end ? per : end;hash[per] += per;}// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额int prv = hash[0]; // dp[0]int cur = max(hash[0], hash[1]); // dp[1]for (int i = 2; i <= end; i++){// dp[k] = max(dp[k - 1], hash[k] + dp[k - 2]);int tmp = max(cur, hash[i] + prv);prv = cur;cur = tmp;}cout << cur << endl;return 0;
}
相关文章:
【算法-动态规划】打家劫舍专题
文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍 198. 打家劫舍 - 力扣(LeetCode) 1.1一维数…...
关于技术管理者的一些思考
前 言 在软件开发领域,当一名资深工程师有机会成为一名技术管理者的时候,通常他/她的反应是什么?兴奋、担扰、无奈还是推托,具体是什么心情也许对结果并不重要,更加重要是在一刻,我们一定要问问我们内心的…...
Alpha-CLIP: A CLIP Model Focusing on Wherever You Want CVPR 2024
在原始的接受RGB三通道输入的CLIP模型的上额外增加了一个alpha通道。在千万量级的RGBA-region的图像文本对上进行训练后,Alpha-CLIP可以在保证CLIP原始感知能力的前提下,关注到任意指定区域。 GitHub - SunzeY/AlphaCLIP: [CVPR 2024] Alpha-CLIP: A CLI…...
Golang | Leetcode Golang题解之第495题提莫攻击
题目: 题解: func findPoisonedDuration(timeSeries []int, duration int) (ans int) {expired : 0for _, t : range timeSeries {if t > expired {ans duration} else {ans t duration - expired}expired t duration}return }...
04 go语言(golang) - 变量和赋值过程
变量 在Go语言中,变量的定义和初始化是编程的基础部分。Go提供了多种方式来声明和初始化变量,以适应不同的使用场景。 基本变量声明 使用var关键字: 使用var关键字可以在函数内部或外部声明变量。如果在函数外部声明,该变量为全…...
语言/图像/视频模型一网打尽!BigModel大模型开放平台助力开发者轻松打造AI新应用!
2024年8⽉28⽇,在ACM SIGKDD(国际数据挖掘与知识发现⼤会,KDD)上会议现场,智谱AI重磅推出了新⼀代全⾃研基座⼤模型 GLM-4-Plus、图像/视频理解模型 GLM-4V-Plus 和⽂⽣图模型 CogView3-Plus。这些新模型,已…...
Go语言Linux环境搭建以编写第一个Go程序
目录 文章目录 目录Go语言入门1、说明2、CentOS7安装Go3、编写第一个程序3.1、编写程序3.2、运行程序3.3、生成二进制文件4、编写第一个web程序4.1、编写代码4.2、运行程序4.3、测试访问4.4、生成二进制配置Vim-go语法高亮1)、下载和设置Vundle.vim(vim安装插件的工具)2)、…...
使用 Go 构建一个最小的 API 应用
最近有项目要使用 Go 开发,作为一个. NET Core 选手,准备先撸一个包含 CRUD 的最小 MVP 项目练手。 要创建一个 TODO 应用,会创建下面这些接口: APIDescriptionRequest bodyResponse bodyGET /todoitemsGet all to-do itemsNone…...
MySQL 日常维护指南:常见任务、频率及问题解决
MySQL 作为一种广泛使用的开源关系型数据库,随着数据量和应用复杂性的增加,定期的数据库维护对于保持系统高效运行至关重要。通过合理的日常维护,数据库管理员能够确保 MySQL 数据库的稳定性、性能以及数据的完整性。本文将介绍 MySQL 的常见…...
oracle ORA-24920:列大小对于客户机过大
问题描述 在一次读取某个视图数据过程中,当数据读取到x条时,报错ORA-24920:列大小对于客户机过大。 通过查询资料得知,oracle 数据库升级到了12c,VARCHAR2的容量也从4000升级到了32767。 所以猜测某个字段的长度超过4…...
使用 Docker compose 部署 Nacos(达梦数据库)
1. 制作镜像的源码地址 https://github.com/wangsilingwsl/nacos-dm.git 参考的开源项目:https://github.com/jeecgboot/JeecgBoot/tree/master/jeecg-boot/jeecg-server-cloud/jeecg-cloud-nacos (master分支;tag:v3.7.1&#…...
人工智能 | 阿里通义千问大模型
简介 通义千问系列模型为阿里云研发的大语言模型。千问模型基于 Transformer 架构,在超大规模的预训练数据上进行训练得到。预训练数据类型多样,覆盖广泛,包括大量网络文本、专业书籍、代码等。同时,在预训练模型的基础之上&…...
Windows环境下Qt Creator调试模式下qDebug输出中文乱码问题
尝试修改系统的区域设置的方法: 可以修复问题。但会出现其它问题: 比如某些软件打不开,或者一些软件界面的中文显示乱码! 暂时没有找到其它更好的办法。...
java防止表单重复提交的注解@RepeatSubmit
代码解释 RepeatSubmit 是一个自定义注解,通常用于防止表单重复提交。这个注解可以应用于控制器方法上,以确保同一个请求在一定时间内不会被多次提交。以下是一些常见的参数和用法: value: 注解的名称或描述。 interval: 两次请求之间的最小间…...
HTTP快速入门
HTTP报文结构 HTTP 协议主要由三大部分组成: ● 起始行(start line):描述请求或响应的基本信息; ● 头部字段(header):使用 key-value 形式更详细地说明报文; ● 消息正…...
Nacos简介
Nacos是一个开源的动态服务发现、配置管理和服务管理平台,由阿里巴巴集团开发并开源。它提供了服务注册与发现、配置管理、动态DNS服务、服务健康监测、权重和流量管理等核心特性,非常适合构建云原生应用和微服务架构。 Nacos的核心功能包括:…...
基于深度学习的稳健的模型推理与不确定性建模
基于深度学习的稳健模型推理与不确定性建模,是现代AI系统中至关重要的研究方向。随着深度学习在各类应用中的成功,如何保证模型在面对未知或不确定性输入时仍能做出稳健的推理,并能够量化这种不确定性,成为关键问题。稳健性与不确…...
C语言 sizeof 的介绍,以及sizeof计算数组名、 数组首地址、数组的元素之间的区别
一、sizeof 介绍 sizeof 是 C 语言中的一个运算符,用于计算数据类型或变量在内存中占用的字节数。用于计算数据类型或变量所占的内存大小,以字节为单位。它可以在编译时计算其操作数的大小,并返回一个 size_t 类型的值。它可以帮助了解不同类…...
深入理解Oracle闪回技术
引言: Oracle 闪回(Flashback)是一组强大的功能,用于恢复数据库中的数据或对象到过去的某个时间点或状态,而无需进行传统的基于备份和恢复的操作。 Oracle 闪回的主要类型 1. 闪回查询(Flashback Query&…...
Go 语言初探
Google 公司有一个传统,允许员工利用 20% 的工作时间开发自己的实验项目。2007 年 9月,UTF-8 的设计者之一 Rob Pike(罗布.皮克)在 Google 的分布式编译平台上进行 C++ 编译时,与同事 Robert Griesemer (罗布.格里泽默)在漫长的等待中讨论了编程语言面临的主要问题。他们一…...
业绩大增37%,订单超210亿!博泰车联财报释放强信号,龙头未来可期
日前,博泰车联交出了上市后的首份亮眼「成绩单」。财报显示,博泰车联2025年全年实现营收35.1亿元,较上年大幅增长37.26%;过去的几年间,博泰车联的营收规模实现爆发式增长,年复合增长率达44.9%。这种高增长态…...
firefly_star
Qt是一个跨平台C图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本笔记将重点介绍QSpinBox数值微调组件的常用方法及灵活应用。…...
暗黑破坏神2存档修改终极指南:告别十六进制编辑,3步完成角色定制
暗黑破坏神2存档修改终极指南:告别十六进制编辑,3步完成角色定制 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor d2s-editor是一款专为《暗黑破坏神2》玩家设计的Web存档编辑器,通过直观的可视…...
如何用30美元自制AI智能眼镜?OpenGlass开源项目全解析
如何用30美元自制AI智能眼镜?OpenGlass开源项目全解析 【免费下载链接】OpenGlass Turn any glasses into AI-powered smart glasses 项目地址: https://gitcode.com/GitHub_Trending/op/OpenGlass 想象一下,你正在博物馆参观,眼前是一…...
万兆光模块:网络提速的核心引擎
在数字化转型的浪潮中,数据已成为核心生产要素,而连接数据的网络,则是决定其流动速度与效率的关键。当我们沉浸在4K/8K的视觉盛宴中,惊叹于云游戏的即时交互,或是受益于远程医疗的精准诊断时,背后都离不开一…...
LTR-329ALS-01环境光传感器驱动与I²C配置详解
1. LTR-329ALS-01 数字环境光传感器深度技术解析1.1 器件定位与系统级设计考量LTR-329ALS-01 是一款面向低功耗嵌入式应用的 IC 接口数字环境光传感器(Ambient Light Sensor, ALS),由 Lite-On 公司设计,广泛应用于智能手机、可穿戴…...
QWEN-AUDIO与其他AI工具共存:如何合理分配GPU资源?
QWEN-AUDIO与其他AI工具共存:如何合理分配GPU资源? 1. 多AI工具共存的挑战与解决方案 在当前的AI应用场景中,单一GPU服务器往往需要同时运行多个AI模型。QWEN-AUDIO作为一款高性能语音合成系统,如何与其他视觉、语言模型和谐共存…...
Qwen2.5-VL-7B-Instruct新手必看:无需网络,纯本地部署的多模态AI工具
Qwen2.5-VL-7B-Instruct新手必看:无需网络,纯本地部署的多模态AI工具 你是不是经常遇到这样的场景:看到一张复杂的图表,想快速提取里面的数据;收到一张产品照片,需要生成详细的描述文案;或者想…...
从Eclipse转IntelliJ IDEA的老司机踩坑记:20个必改设置让你的迁移过程更顺滑
从Eclipse转IntelliJ IDEA的老司机踩坑记:20个必改设置让你的迁移过程更顺滑 第一次打开IntelliJ IDEA时,那种既熟悉又陌生的感觉会让任何Eclipse老手感到不安。菜单栏去哪了?我的项目视图怎么变了?为什么快捷键全都不对ÿ…...
Graphormer保姆级教学:Supervisor配置文件(graphormer.conf)逐行注释
Graphormer保姆级教学:Supervisor配置文件(graphormer.conf)逐行注释 1. Graphormer简介 Graphormer是一种基于纯Transformer架构的图神经网络,专门为分子图(原子-键结构)的全局结构建模与属性预测而设计…...
