【算法-动态规划】打家劫舍专题
文章目录
- 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 (罗布.格里泽默)在漫长的等待中讨论了编程语言面临的主要问题。他们一…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
