代码随想录算法训练营 Day41 动态规划3
Day41 动态规划3
343. 整数拆分
思路
不知道如何拆分,才能使乘积最大化
有什么理论依据?
根据代码随想录
拆分使乘积最大化逻辑:应该尽可能拆成相同的数
根据题目,发现,拆分后的数可以继续拆分,因此可以用动规的思路
要点:
- dp数组含义 对i进行拆分,得到最大乘积为dp[i]
- 递推公式:
如果拆成两个数:j * (i - j)
如果拆成三个数以上:j * dp[i - j]
递推公式可以将所有的情况都考虑,在比较取最大值就行;因此不知道上述逻辑也能写
最终代码:
class Solution:def integerBreak(self, n: int) -> int:dp = [0] * (n + 1)dp[0] = 0dp[1] = 0dp[2] = 1for i in range(3, n + 1):for j in range(1, i // 2 + 1):dp[i] = max(j * (i - j), j * dp[i - j], dp[i])return dp[n]
总结:
一开始不知道怎么拆最大,觉得会有一个特别的逻辑,但是实际写代码的时候,是一个暴力的方式将所有的情况都考虑,再比较取值的。
96.不同的二叉搜索树
思路
dp[i]的结果可以看作根节点为1到i的二叉搜索树种数之和
但是不同n,根节点为i得到的结果也不同
不知道怎么想递推公式
根据代码随想录
首先,根据样例观察规律
n = 3
1为根节点以及3为根节点,右子树的分布和n为2的布局是一样的
2为根节点,左右子树的分布根n为1一样
总共和 = 根节点为1的情况 + 根节点为2 + 根节点为3
根节点为1 = 左子树0个节点 * 右子树2个节点
根2 = 左子树1个节点 * 右子树1个节点
根3 = 左子树2个节点 * 右子树0个节点
n = 3可以根据0,1,2三种情况推导出来
j 为根节点,左边有j - 1个节点,右面有i - j个节点
最终代码:
class Solution:def numTrees(self, n: int) -> int:dp = [0] * (n + 1)dp[0] = 1for i in range(1, n + 1):for j in range(1, i + 1):dp[i] += dp[j - 1] * dp[i - j]return dp[n]
总结
这题有点难,没做过想不到怎么做
相关文章:
代码随想录算法训练营 Day41 动态规划3
Day41 动态规划3 343. 整数拆分 思路 不知道如何拆分,才能使乘积最大化 有什么理论依据? 根据代码随想录 拆分使乘积最大化逻辑:应该尽可能拆成相同的数 根据题目,发现,拆分后的数可以继续拆分,因此可…...

面试题:反推B+树高度
一个表5000w数据,一个数据行大小为1k,主键为long类型数据,假设指针大小为8B,页大小为16K,求B树的高度? B树的非叶子节点存储key和指针,叶子节点存储数据,对应表中的某些行。 叶子节点…...

瑞吉外卖实战学习--11、分类管理的列表分页查询
分类管理的列表分页查询 前言1、创建接口2、基于分页组件来实现的 前言 通过前端接口可以看到请求和传递的参数,本文章是基于mybatisPlus的分页插件来实现的 1、创建接口 GetMapping("/page")public R<Page> page(int page,int pageSize){ // …...

网络安全新视角:数据可视化的力量
在当今数字化时代,网络安全已成为各大企业乃至国家安全的重要组成部分。随着网络攻击的日益复杂和隐蔽,传统的网络安全防护措施已难以满足需求,急需新型的解决方案以增强网络防护能力。数据可视化技术,作为一种将复杂数据转换为图…...

Aurora8b10b(2)上板验证
文章目录 前言一、AXI_Stream数据产生模块二、上板效果总结 前言 上一篇内容我们已经详细介绍了基于aurora8b10b IP核的设计,本文将基于此进一步完善并且进行上板验证。 设计思路及代码思路参考FPGA奇哥系列网课 一、AXI_Stream数据产生模块 AXIS协议是非常简单的…...

每天五分钟计算机视觉:使用神经网络完成人脸的特征点检测
本文重点 我们上一节课程中学习了如何利用神经网络对图片中的对象进行定位,也就是通过输出四个参数值bx、by、bℎ和bw给出图片中对象的边界框。 本节课程我们学习特征点的检测,神经网络可以通过输出图片中对象的特征点的(x,y)坐标来实现对目标特征的识别,我们看几个例子。…...

表白墙项目(JAVA实现)
1、在html里 class使用. id使用# 2、记得引入响应依赖(举例lombok) 3、messageController package com.example.demo.demos.web; import org.springframework.util.StringUtils; import org.springframework.web.bind.annotation.RequestMapping; i…...
openGauss 高级分析函数支持
高级分析函数支持 可获得性 本特性自openGauss 1.1.0版本开始引入。 特性简介 无。 客户价值 我们提供窗口函数来进行数据高级分析处理。窗口函数将一个表中的数据进行预先分组,每一行属于一个特定的组,然后在这个组上进行一系列的关联分析计算。这…...

【Java面试题系列】基础篇
目录 基本常识标识符的命名规则八种基本数据类型的大小,以及他们的封装类3*0.10.3返回值是什么short s1 1; s1 s1 1;有什么错? short s1 1; s1 1;有什么错?简述&&与&的区别?简述break与continue、return的区别?Arrays类的…...
Ubuntu 23.04 安装es
在Ubuntu 23.04上安装Elasticsearch的过程可能与之前版本类似,以下是基于最新稳定版Elasticsearch的一般安装步骤: 准备工作: 确保系统已更新至最新版本: sudo apt update && sudo apt upgrade安装Java Development Kit (…...
gradle 7.0 + 配置
Maven 镜像地址的设置 原来在项目根目录的 build.gradle 中进行设置,但是现在里面只有plugins。 工程的build.gradle的dependencies修改为plugins,替代了引用原来的Gradle版本。 // Top-level build file where you can add configuration options com…...
vue3的ref和reactive对比
一,ref 作用: 定义一个 ref 响应式的数据语法: const xxx ref(initValue) 用法 创建一个包含响应式数据的引用对象(reference对象,简称ref对象)。 JS中操作数据: xxx.value 模板中读取数据: 不需要.value࿰…...

是否应该升级到ChatGPT 4.0?深度对比ChatGPT 3.5与4.0的差异
如果只是想简单地体验AI的魅力,感受大模型的独特之处,或是玩一玩文字游戏,那么升级至ChatGPT 4.0可能并非必需。然而,若你期望将AI作为提升工作学习效率的得力助手,那么我强烈建议你升级到ChatGPT 4.0。 如果你不知道…...

C++刷题篇——04找等值元素
一、题目 二、解题思路 1、分割后放进二维数组 2、使用map,key为数值,value为其坐标 3、遍历二维数组元素,再在map中找该元素对应的value值(二维数组形式),倘若value.size为1,那直接返回-1&…...

2024年最新服装erp软件排名!(建议收藏)
随着数字经济时代的到来,传统服装生产企业正在经历深刻的变革。如何实现产业数字化升级,是众多服装企业面临的共同课题。当前,服装类的企业管理软件已经成为企业实现智能化转型的关键。面对已经发生深刻改变的商业竞争环境,传统的…...

Radash一款JavaScript最新的实用工具库,Lodash的平替!
文章目录 Lodash 的痛点进入正题--Radash特点 举例几个常用的api 一说lodash应该大部分前端同学都知道吧,陪伴我们好多年的JavaScript工具库,但是自从 ES6 出现后就慢慢退出前端人的视线,能ES6写的代码绝对不会用Lodash,也不是完全…...

使用node爬取视频网站里《龙珠》m3u8视频
1. 找到视频播放网站 百度一下 龙珠视频播放 精挑细选一个可以播放的网站。 如:我在网上随便找了一个播放网站,可以直接在线播放 https://www.xxx.com/play/39999-1-7.html 这里不具体写视频地址了,大家可以自行搜索 2.分析网页DOM结…...

搜索与图论——Prim算法求最小生成树
在最小生成树问题里,正边和负边都没问题 朴素版prim算法 时间复杂度O(n^2) 生成树:每一次选中的t点,它和集合的距离对应的那条边,就是生成树的一条边 算法流程和dijkstra算法非常相似 #include<iostream> #include<cs…...
sqlmap基础知识
一、sqlmap简介 sqlmap是一个开源的渗透测试工具,可以自动检测和利用SQL注入漏洞以及接管数据库服务器的过程。 官网: sqlmap.org 核心功能 漏洞检测漏洞利用 学习关键点 基于sqlmap进行sql注入漏洞的检测,注入利用和攻击基于sqlmap进…...
读《C Primer Plus》
1、汇编语言是为特殊的中央处理单元设计的一系列内部指令,使用助记符来表示;不同的CPU系列使用不同的汇编语言。 2、C语言充分利用计算机优势,使它具有汇编语言才有的微调控能力,可移植性极好。 3、C语言可以访问硬件、操作内存…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...

五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

使用VMware克隆功能快速搭建集群
自己搭建的虚拟机,后续不管是学习java还是大数据,都需要集群,java需要分布式的微服务,大数据Hadoop的计算集群,如果从头开始搭建虚拟机会比较费时费力,这里分享一下如何使用克隆功能快速搭建一个集群 先把…...