简单多状态dp【动态规划】
目录
一、按摩师
二、打家劫舍
三、删除并获得点数
四、粉刷房子
五、买卖股票的最佳时机
六、买卖股票的最佳时机(含手续费)
七、买卖股票的最佳时机III
八、买卖股票的最佳时机IV
一、按摩师


class Solution { public:int massage(vector<int>& nums) {int n =nums.size();if(n == 0) return 0;vector<int> f(n);auto g = f;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]);} };
二、打家劫舍


class Solution {
public:int rob1(vector<int>& nums,int l,int r) {if(l>r) return 0;int n =nums.size();if(n == 0) return 0;vector<int> f(n);auto g = f;f[l] = nums[l];for(int i = l;i <= r;i++){f[i] = g[i-1] + nums[i];g[i] = max(f[i-1],g[i-1]);}return max(f[r],g[r]);}int rob(vector<int>& nums) {int n = nums.size();int ret1 = rob1(nums,2,n-2)+nums[0];int ret2 = rob1(nums,1,n-1);return max(ret1,ret2);}
};
三、删除并获得点数

class Solution {
public:int deleteAndEarn(vector<int>& nums) {int n = nums.size();const int N = 10001;int arr[N] = {0}; for(auto e : nums){arr[e] += e;}vector<int> f(N);auto g = f;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]);}
};
四、粉刷房子



class Solution {
public: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] = costs[i-1][0] + min(dp[i-1][1],dp[i-1][2]);dp[i][1] = costs[i-1][1] + min(dp[i-1][0],dp[i-1][2]);dp[i][2] = costs[i-1][2] + min(dp[i-1][0],dp[i-1][1]);}return min(dp[n][0],min(dp[n][1],dp[n][2]));}
};
五、买卖股票的最佳时机


class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(3));dp[0][0] = -prices[0];for(int i = 1;i < n;i++){dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i]);dp[i][1] = max(dp[i-1][1],dp[i-1][2]);dp[i][2] = dp[i-1][0]+prices[i];}return max(dp[n-1][1],dp[n-1][2]);}
};
六、买卖股票的最佳时机(含手续费)
上一题用的是二维数组的第二维来表示多种状态,是因为状态比较多,如果像此题只有两种状态,就可以用两个函数,本质上是一样的。


class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<int> f(n);auto g = f;f[0] = -prices[0];for(int i = 1;i < n;i++){f[i] = max(f[i-1],g[i-1] - prices[i]);g[i] = max(g[i-1],f[i-1]+prices[i]- fee);}return g[n-1];}
};
七、买卖股票的最佳时机III
class Solution {
public:const int INF = 0x3f3f3f3f;int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n,vector<int>(3,-INF));auto g = f;f[0][0] = -prices[0];g[0][0] = 0;for(int i = 1;i < n;i++){for(int j = 0;j < 3;j++){f[i][j] = max(f[i-1][j],g[i-1][j] - prices[i]);g[i][j] = g[i-1][j];if(j >= 1)g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);}} int ret = 0;for(int i = 0;i < 3;i++){ret = max(ret,g[n-1][i]);}return ret;}
};
八、买卖股票的最佳时机IV

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();k = min(k,n/2); const int INF = 0x3f3f3f3f;vector<vector<int>> f(n,vector<int>(k+1,-INF));//注意是k+1auto g = f;f[0][0] = -prices[0];g[0][0] = 0;for(int i = 1;i < n;i++){for(int j = 0;j <= k;j++){f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j] = g[i-1][j];if(j >= 1)g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);}}int ret = 0;for(int j = 0;j <= k;j++){ret = max(ret,g[n-1][j]);}return ret;}
};
相关文章:
简单多状态dp【动态规划】
目录 一、按摩师 二、打家劫舍 三、删除并获得点数 四、粉刷房子 五、买卖股票的最佳时机 六、买卖股票的最佳时机(含手续费) 七、买卖股票的最佳时机III 八、买卖股票的最佳时机IV 一、按摩师 class Solution { public:int massage(vector<int>…...
OpenCV中initUndistortRectifyMap ()函数与十四讲中去畸变公式的区别探究
文章目录 1.十四讲中的去畸变公式2. OpenCV中的去畸变公式3. 4个参数和8个参数之间的区别4.initUndistortRectifyMap()函数源码 最近在使用OpenCV对鱼眼相机图像去畸变时发现一个问题,基于针孔模型去畸变时所使用的参数和之前十四讲以及视觉SLAM中的畸变系数有一点不…...
【C++】C++11——智能指针、内存泄漏、智能指针的使用和原理、RAII、auto_ptr、unique_ptr、shared_ptr、weak_ptr
文章目录 C117.智能指针7.1内存泄漏7.2智能指针的概念7.3智能指针的使用7.3.1 auto_ptr7.3.2 unique_ptr7.3.3 shared_ptr7.3.4 weak_ptr C11 7.智能指针 7.1内存泄漏 什么是内存泄漏: 内存泄漏指因为疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏…...
EDUSRC-记某擎未授权与sql注入
目录 360天擎 - 未授权与sql注入 信息收集 FOFA语法 鹰图搜索 360天擎未授权访问 - 数据库信息泄露 漏洞复现 修复方案 360天擎终端安全管理系统ccid处SQL注入 漏洞复现 手动测试方法 修复方案 360天擎 - 未授权与sql注入 通常访问的页面如下,存在登录框…...
1688拍立淘API接口分享
拍立淘接口,顾名思义,就是通过图片搜索到相关商品列表。通过此接口,可以实现图片搜索爆款商品等功能。 接口地址:1688.item_search_img 公共参数 名称类型必须描述keyString是调用key(必须以GET方式拼接在URL中&…...
昇腾910使用记录
一. 压缩文件和解压文件 1. 压缩文件 tar -czvf UNITE-main.tar.gz ./UNITE-main/2. 解压文件 tar -xvf ./UNITE-main/二. CUDA更改为NPU data[label] data[label].cuda() data[instance] data[instance].cuda() data[image] data[image].cuda()更改为 data[label] da…...
从一部iPhone手机看芯片的分类
目录 问题 iPhone X 手机处理器:A11 iPhone X 的两大存储芯片 数字 IC CPU:计算设备的运算核心和控制核心 GPU:图形处理器 ASIC:为解决特定应用问题而定制设计的集成电路 存储芯片:DRAM 和 NAND Flash iPhone…...
arm day 7
完成字符串收发函数的封装并且验证现象,一个字符串发送接受后会有‘\n’ \r src/uart.c #include"uart.h"void uart4_init() {//设置UART4的RCc时钟使能//RCC_MP_APB1ENSETR[16]->1RCC->MP_APB1ENSETR | (0x1<<16);//设置GPIOB和GPIOG的时钟…...
Java基础面试-面向对象
什么是面向对象? 对比面向过程,是两种不同的处理问题角度 面向过程更注重事情的每一个步骤及顺序,面向对象更注重事情有哪些参与者(对象),及各自需要做什么 比如洗衣机洗衣服 面向过程会将任务拆解成一系…...
GCC vs. G++:C 与 C++ 编译器的差异和比较
本文将介绍 GCC(GNU Compiler Collection)和 G 编译器的区别,并对它们在 C 和 C 程序开发中的特性和用法进行比较和总结。 引言 在 C 和 C 程序开发中,选择合适的编译器是至关重要的。GCC(GNU Compiler Collection&a…...
MAC m系列docker login报错
错误:ERROR: failed to solve: XXX error getting credentials - err: exit status 1, out: 解决: vi ~/.docker/config.jsonzsxzsx [15时55分55秒] [~] { {"auths": {"harbor-g42c.corp.matrx.team": {"auth": "…...
Redis通用指令和五大基本数据类型常用指令总结
通用指令 keys parttern 查询key (parttern即通配符,不是正则表达式,例如 keys a? 匹配以a开头的长度为2的key) del key 删除key exists key 获取key是否存在 type key 获取key的类型 expire key seconds 为指定key设置有效期,单位秒 …...
uCharts常用图表组件demo
带渐变阴影的曲线图 <view class"charts-box"><qiun-data-charts type"area" :opts"opts" :chartData"chartData" :ontouch"true":background"rgba(256,256,256,0)" /> </view>data(){return{…...
VNC:Timed out waiting for a response from the computer
VNC的服务端使用的是TigerVNC,客户端使用的是RealVNC TigerVNC按其他博客配好后,防火墙ip什么的都配了,vnc客户端怎么连都是超时。 这里建议大家可以尝试一下重启服务器。我的是CentOS的 shutdown -r now 配了2天,最后服务器重启…...
Kotlin 协程 知识点
Android 上的 Kotlin 协程 | Android Developers (google.cn) 官方网址 1.什么是协程? 我觉得协程就是kotlin中一种优雅的实现异步请求 协程(Coroutines)是一种轻量级的并发编程概念,旨在简化异步编程和并发任务的处理。它是…...
简单大方的自我介绍 PPT 格式
自我介绍是展示自己的机会,同时也是展现自信和魅力的重要时刻。通过简单大方的PPT格式,可以更好地展示自己的个性和才华。下面是一些建议,帮助你在自我介绍中展现自信和魅力。 1. 打造简洁而有吸引力的PPT布局: - 选择简洁大方的背…...
panads操作excel
panads简介 pandas是基于Numpy创建的Python包,内置了大量标准函数,能够高效地解决数据分析数据处理和分析任务,pandas支持多种文件的操作,比如Excel,csv,json,txt 文件等,读取文件之…...
【MySQL】联合查询、子查询、合并查询
这里提供了三个表: 表1: mysql> select * from class; -------------- | id | name | -------------- | 1 | 一班 | | 2 | 二班 | | 3 | 三班 | -------------- 3 rows in set (0.01 sec) 表2: mysql> select * fro…...
小程序中如何设置所服务地区的时区
在全球化的背景下,小程序除了在中国使用外,还为海外的华人地区提供服务。例如我们采云小程序为泰国、阿根廷、缅甸等国家的商家就提供过微信小程序。这些商家开通小程序,为本地的华人提供服务。但通常小程序的开发者/服务商位于中国ÿ…...
Linux环境安装mysql8.0
1个人习惯我喜欢给软件安装在/use/local下,我使用的finalshell软件,直接手动新建一个文件夹名字为mysql 2下载mysql wget https://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-8.0.20-linux-glibc2.12-x86_64.tar.xz 3解压文件 tar -xvf mysql-8.0.2…...
JetBrains IDE 30天试用重置:一键解决方案的完整实践指南
JetBrains IDE 30天试用重置:一键解决方案的完整实践指南 【免费下载链接】ide-eval-resetter 项目地址: https://gitcode.com/gh_mirrors/id/ide-eval-resetter 当您正专注于代码调试时,IDE突然弹出"评估期已结束"的红色警告…...
AI智能体操作安卓设备:基于agent-droid-bridge的自动化实践
1. 项目概述:连接AI与安卓设备的桥梁 最近在折腾AI智能体(Agent)和自动化流程时,遇到了一个挺有意思的需求:如何让运行在服务器上的AI程序,直接去操作一台真实的安卓手机或模拟器,完成一些复杂的…...
柔性3D打印与生物仿生设计:从TPU材料到空气喷涂的完整实践
1. 项目概述:当柔性3D打印遇上生物仿生美学如果你和我一样,玩3D打印玩久了,总会对那些千篇一律的硬质塑料件感到一丝审美疲劳。我们总在追求更高的精度、更强的结构,却常常忽略了材料本身可以带来的、截然不同的体验。直到我开始接…...
Arduino nRF52 BLE开发:GATT服务与特征值配置实战详解
1. 项目概述如果你正在用Arduino和nRF52系列芯片(比如nRF52832或nRF52840)做蓝牙低功耗(BLE)开发,那你肯定绕不开GATT(通用属性配置文件)这一关。GATT是BLE通信的“语言规则”,它定义…...
量子最优控制中的iLQR算法实践与优化
1. 量子最优控制基础与挑战量子最优控制(Quantum Optimal Control, QOC)是现代量子计算中的核心技术,其核心目标是通过精心设计的控制脉冲序列,实现对量子系统状态演化的精确操控。在超导量子计算体系中,这一技术尤为重…...
深度解析VS Code Live Server:高效前端开发实时预览配置秘籍
深度解析VS Code Live Server:高效前端开发实时预览配置秘籍 【免费下载链接】vscode-live-server Launch a development local Server with live reload feature for static & dynamic pages. 项目地址: https://gitcode.com/gh_mirrors/vs/vscode-live-serv…...
龙芯3A6000平台Loongnix系统部署实战:从固件更新到驱动配置全解析
1. 项目概述:一次国产平台上的系统部署实战最近,我拿到了一台基于龙芯3A6000处理器和7A2000桥片的国产台式机。对于长期在x86/ARM生态里打转的开发者来说,这无疑是一个充满新鲜感和挑战的“新玩具”。它的核心使命,就是运行龙芯社…...
在 1688、阿里国际站上,怎么分清哪些是真工厂、哪些是贸易商?一份采购辨别清单
跨境卖家和采购最常踩的坑,就是把贸易商当成了源头工厂。结果是:报价里多了一手差价、打样要等贸易商再转给后面的厂、出了质量问题没人能进车间整改。 平台上的"工厂认证"“源头工厂”"工厂直供"标签,看起来像是替你做了…...
PaperDebugger:解决机器学习代码复现危机的调试框架
1. 项目概述:当代码遇上论文,一场“可复现性”的硬仗如果你和我一样,常年混迹在机器学习、数据科学或者计算物理这类前沿领域,那你一定对下面这个场景不陌生:读到一篇顶会论文,作者声称他们的模型在某个基准…...
ESP-SR深度解析:嵌入式语音识别系统的架构设计与性能优化实战指南
ESP-SR深度解析:嵌入式语音识别系统的架构设计与性能优化实战指南 【免费下载链接】esp-sr Speech recognition 项目地址: https://gitcode.com/gh_mirrors/es/esp-sr 在物联网设备智能化浪潮中,语音交互已成为人机交互的重要入口。ESP-SR作为乐鑫…...
