day-41 代码随想录算法训练营(19)动态规划 part 03
343.整数拆分
思路:
- 1.dp存储的是第i个数,拆分之后最大乘积
- 2.dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
- 3.初始化:dp[0]=dp[1]=0,dp[2]=1;
- 4.遍历顺序:外层循环 3-n,内层循环 1-i
2.涉及两次取max:
- dp[i] 表示拆开的最大乘积,因为涉及多次计算
- j*(i-j) 表示拆成两个数
- j*dp[i-j] 表示拆成两个以上的数(dp[i-j] 就是剩下没拆的数,拆开的最大乘积)
class Solution {
public:int integerBreak(int n) {vector<int>dp(n+1,0);dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<i;j++){dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));cout<<i<<" "<<dp[i]<<endl;}}return dp[n];}
};

96.不同的二叉搜索树
分析:1-n有几种二叉搜索树
-
1.以1-n每个数为根节点
-
2.判断根节点左边和右边各有几个节点,只有结点数相同,组合的二叉搜索树种数就是一样的。
思路:
- 1.dp存储n个节点有多少种二叉搜索树
- 2.dp[i]=dp[i-1]*dp[n-i];
- 3.初始化:dp[0]=dp[1]=1,dp[2]=2;
- 4.遍历顺序:3-n
416.分割等和子集
分析:
- 数组要求分成两个等和子集,所以一定要有子集和为总和的一半
- 转换为:在集合中找数字,看能否组合成总和的一半值的子集
- 转换为:在总和一半容量的背包里,寻找子集刚好装满
思路一:
1.dp存储:容量为 j 时,装入物品的最大值
2.dp [ j ] =max ( dp [ j ] ,dp [ j - nums [i] ] + nums [ i ] )
3.初始化:所有值初始化为0
4.遍历顺序:外层遍历数字(顺序,物品),内层遍历数字(倒序,背包容量)
class Solution {
public:bool canPartition(vector<int>& nums) {int total=0;for(auto it:nums) total+=it;//求出总和if(total%2!=0) return false;//过滤不可拆成两半的情况int target=total/2;//背包容量vector<int>dp(10001,0);for(int i=0;i<nums.size();i++){//遍历物品for(int j=target;j>=nums[i];j--){//背包容量递减,最少能装入一个物品dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);//dp[j] 是不装当前物品//dp[j-nums[i]]+nums[i] 是装当前物品}}if(dp[target]==target) return true;//背包容量为target,装了target重的物品return false;}
};
相关文章:
day-41 代码随想录算法训练营(19)动态规划 part 03
343.整数拆分 思路: 1.dp存储的是第i个数,拆分之后最大乘积2.dp[i]max(dp[i],max(j*(i-j),j*dp[i-j]));3.初始化:dp[0]dp[1]0,dp[2]1;4.遍历顺序:外层循环 3-n,内层循环 1-i 2.涉及两次取max: dp[i] 表…...
K8S安装部署 初始化操作(一)
准备好服务器和服务器资源 ip hostnameip资源 (2核2G也可以)k8s-master 192.168.37.1184核 4G 40G硬盘k8s-node1192.168.37.1192核 2G 20G硬盘k8s-node2192.168.37.1202核 2G 20G硬盘 初始操作三台同时执行 1、关闭防火墙 [rootlocalhost ~]# s…...
【多线程案例】单例模式(懒汉模式和饿汉模式)
文章目录 1. 什么是单例模式?2. 立即加载/“饿汉模式”3. 延时加载/“懒汉模式”3.1 第一版3.2 第二版3.3 第三版3.4 第四版 1. 什么是单例模式? 提起单例模式,就必须介绍设计模式,而设计模式就是在软件设计中,针对特殊…...
Anaconda - 操作系统安装程序 简要介绍
Anaconda 简要介绍 1. Anaconda 简介2. Anaconda 体系结构3. Anaconda 开发模型4. Anaconda 启动概述5. Anaconda 源码1. 接口2. 自定义组件3. 硬盘分区:使用python-blivet包4. Bootloader5. 各个步骤的配置:6. 安装软件包:7. 安装控制&#…...
【数据库设计】向量搜索HNSW算法优化
做向量存储的过程中,遇到向量搜索的情况处理,HNSW算法是目前向量搜索的主要算法之一,采用的是图算法,主要的问题是使用内存大,训练时间长。做算法优化过程中获得部分技巧,分享出来。 一、算法本身的优化 对…...
多通道振弦数据记录仪应用桥梁安全监测的关键要点
多通道振弦数据记录仪应用桥梁安全监测的关键要点 随着近年来桥梁建设和维护的不断推进,桥梁安全监测越来越成为公共关注的焦点。多通道振弦数据记录仪因其高效、准确的数据采集和处理能力,已经成为桥梁安全监测中不可或缺的设备。本文将从以下几个方面…...
深入了解HTTP代理的工作原理
HTTP代理是一种常见的网络代理方式,它可以帮助用户隐藏自己的IP地址,保护个人隐私和安全。了解HTTP代理的工作原理对于使用HTTP代理的用户来说非常重要。本文将深入介绍HTTP代理的工作原理。 代理服务器的作用 HTTP代理的工作原理基于代理服务器的作用。…...
2023年高教社杯数学建模国赛选题人数+C题进阶版修改思路详解
C题思路 修改版 C题保奖 数据预处理 3σ原则 区间判断法、人为判定 问题 1 聚类分析进行简单的分类 相互关系 数据服从正态分布(K-S检验等判定分布类型后) 才能做person相关性 图表结合(热力图、数据结果表) 分布规律 宏…...
第三章微服务配置中心
文章目录 Nacos配置中心统一配置管理在nacos中添加配置文件从微服务拉取配置 配置热更新多环境共享配置 搭建Nacos集群搭建集群初始化数据库配置Nacos启动nginx反向代理 Nacos配置中心 Nacos配置管理 Nacos除了可以做注册中心,同样可以做配置管理来使用。 统一配置…...
箭头函数(arrow function)与普通函数之间的区别是什么?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 语法简洁性:⭐ this 的绑定:⭐ 不能用作构造函数:⭐ 没有 arguments 对象:⭐ 不适用于方法:⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上…...
JMeter 4.0 如何获取cookie
文章目录 前言JMeter 4.0 如何获取cookie1. 修改jmeter.properties 文件2. 添加HTTP Cookie 管理器3. 获取cookie信息 前言 如果您觉得有用的话,记得给博主点个赞,评论,收藏一键三连啊,写作不易啊^ _ ^。 而且听说点赞的人每天…...
【数字IC/FPGA】Verilog中的force和release
在Verilog中,将force用于variable会覆盖掉过程赋值,或者assign引导的连续(procedural assign)赋值,直到release。 下面通过一个简单的例子展示其用法: 加法器代码 module adder ( input logic [31:0] a, …...
进阶C语言-指针的进阶(上)
指针的进阶 📖1.字符指针📖2.指针数组📖3.数组指针🎈3.1 数组指针的定义🎈3.2 &数组名VS数组名🎈3.3 数组指针的使用 📖4.数组参数、指针参数🎈4.1一维数组传参🎈4.2…...
初始化一个 vite + vue 项目
创建项目 首先使用以下命令创建一个vite项目 npm create vite然后根据提示命令 cd 到刚创建的项目目录下,使用npm install安装所需要的依赖包,再使用npm run dev即可启动项目 配置 vite.config.js 添加process.env配置,如果下面 vue-route…...
关于B+树
在数据库管理系统中,使用b树作为索引的数据结构,相比于B树和二叉树,有以下几个好处: b树的非叶子节点只存储关键字和指针,不存储数据,这样可以增加每个节点的关键字数量,降低树的高度ÿ…...
axios 请求和响应拦截器
1. 创建实例 使用 axios.create() 使用自定义配置创建一个 axios 实例。 const $http axios.create({timeout: 1000,headers: {Content-Type: application/json,} })2. 拦截器 在请求或响应被 then 或者 catch 处理前拦截他们,拦截分为请求拦截和响应拦截。 //…...
Element-ui select远程搜索
template部分: <el-form-item label"用户" prop"userId"><el-selectv-model"temp.userId"placeholder"用户"filterableremote:reserve-keyword"false":remote-method"remoteMethod":loading"loadi…...
【Express.js】Docker部署
Docker部署 本节我们来介绍如何使用 Docker 部署 express 应用 准备工作 linux 系统安装好 Docker一个基础的 evp-express-cli 项目,选上 pkg 工具包Docker 的详细用法本文不做介绍,请先自行查阅了解 在 Docker 中部署源码 一个很简单的部署方法就是…...
面试2:通用能力
15丨如何做好开场:给自我介绍加“特效 第一层,满足面试官对信息的期待 这是对自我介绍的基本要求,把个人信息、主要经历、经验和技能有条理地组织起来, 有逻辑地讲出来。需要找出多段经历的关联性和发展变化,形成连…...
zookeeper/HA集群配置
1.zookeep配置 1.1 安装4台虚拟机 (1)按照如下设置准备四台虚拟机,其中三台作为zookeeper,配置每台机器相应的IP,hostname,下载vim,ntpdate配置定时器定时更新时间,psmiscÿ…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
