【算法-动态规划】打家劫舍专题
文章目录
- 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 (罗布.格里泽默)在漫长的等待中讨论了编程语言面临的主要问题。他们一…...
Spring Data Redis实战全攻略:从集群部署到实时流处理
Spring Data Redis实战全攻略:从集群部署到实时流处理 【免费下载链接】spring-data-examples Spring Data Example Projects 项目地址: https://gitcode.com/gh_mirrors/sp/spring-data-examples Spring Data Redis是Spring生态中用于Redis数据存储的核心组…...
Hunyuan-MT-7B多语翻译实战:跨境电商独立站商品页SEO多语内容批量生成
Hunyuan-MT-7B多语翻译实战:跨境电商独立站商品页SEO多语内容批量生成 1. 项目背景与价值 跨境电商独立站面临的最大挑战之一,就是如何为不同语言市场的用户提供本地化的商品内容。传统的人工翻译方式成本高、效率低,而机器翻译又往往无法保…...
Qwen3-14B向量数据库集成:Chroma/Milvus接入与混合检索配置
Qwen3-14B向量数据库集成:Chroma/Milvus接入与混合检索配置 1. 引言:为什么需要向量数据库集成 当你部署了强大的Qwen3-14B大模型后,很快会发现一个关键问题:如何让模型记住并快速检索大量知识?这就是向量数据库的价…...
在Linux中编写shell脚本监听指定端口的实现方式
在Linux中,你可以编写一个shell脚本来监听指定端口。以下是几种实现方式:方法1:使用nc(netcat)的简单监听脚本1234567891011121314151617181920212223#!/bin/bash# 文件名:port_listener.sh# 检查参数if [ …...
从单片机到Linux驱动的技术成长与转型
1. 从单片机到Linux驱动的技术成长之路 刚毕业那会儿,我和大多数电子工程专业的同学一样,怀揣着对技术的无限憧憬。记得大四校招时,我固执地只投递了几家知名大厂的嵌入式开发岗位,甚至在面试时直接报出了远超应届生水平的薪资期望…...
NVIDIA Profile Inspector深度解析:解锁显卡隐藏性能与高级配置实战指南
NVIDIA Profile Inspector深度解析:解锁显卡隐藏性能与高级配置实战指南 【免费下载链接】nvidiaProfileInspector 项目地址: https://gitcode.com/gh_mirrors/nv/nvidiaProfileInspector NVIDIA Profile Inspector是一款面向技术爱好者和开发者的专业显卡配…...
TimesFM时间序列预测模型实战:从基础模型到高效部署的完整路径
TimesFM时间序列预测模型实战:从基础模型到高效部署的完整路径 【免费下载链接】timesfm TimesFM (Time Series Foundation Model) is a pretrained time-series foundation model developed by Google Research for time-series forecasting. 项目地址: https://…...
5G网络架构:核心网、接入网的组成与工作原理
5G网络架构:核心网、接入网的组成与工作原理📝 本章学习目标:本章探讨网络编程,帮助读者掌握网络应用开发技能。通过本章学习,你将全面掌握"5G网络架构:核心网、接入网的组成与工作原理"这一核心…...
先被日本汽车打败,再被中国汽车冲击,欧洲车面临崩盘,已累计裁员50万人!
大众汽车在公布2025年的利润腰斩之后,发布了进一步裁员计划,到2030年将削减5万个工作岗位,占它当下员工总人数的比例大约7.5%,由此业界人士统计了近几年来欧洲诸多车企以及汽车供应链企业宣布的裁员人数,发现欧洲汽车行…...
STM32电位器驱动库:轻量级ADC封装与中值滤波实现
1. 项目概述MentorBit-Potenciometro 是一款专为 MentorBit 系统设计的轻量级电位器(Potentiometer)模块驱动库,面向 STM32 平台(典型为 STM32F4/F7/H7 系列)的嵌入式固件开发。该库并非通用 ADC 抽象层,而…...
