当前位置: 首页 > news >正文

代码随想录算法训练营 Day41 动态规划3

Day41 动态规划3

343. 整数拆分

思路

不知道如何拆分,才能使乘积最大化
有什么理论依据?

根据代码随想录
拆分使乘积最大化逻辑:应该尽可能拆成相同的数

根据题目,发现,拆分后的数可以继续拆分,因此可以用动规的思路

要点:

  1. dp数组含义 对i进行拆分,得到最大乘积为dp[i]
  2. 递推公式:
    如果拆成两个数: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、基于分页组件来实现的 前言 通过前端接口可以看到请求和传递的参数&#xff0c;本文章是基于mybatisPlus的分页插件来实现的 1、创建接口 GetMapping("/page")public R<Page> page(int page,int pageSize){ // …...

网络安全新视角:数据可视化的力量

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

Aurora8b10b(2)上板验证

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

每天五分钟计算机视觉:使用神经网络完成人脸的特征点检测

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

表白墙项目(JAVA实现)

1、在html里 class使用. id使用# 2、记得引入响应依赖&#xff08;举例lombok&#xff09; 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版本开始引入。 特性简介 无。 客户价值 我们提供窗口函数来进行数据高级分析处理。窗口函数将一个表中的数据进行预先分组&#xff0c;每一行属于一个特定的组&#xff0c;然后在这个组上进行一系列的关联分析计算。这…...

【Java面试题系列】基础篇

目录 基本常识标识符的命名规则八种基本数据类型的大小&#xff0c;以及他们的封装类3*0.10.3返回值是什么short s1 1; s1 s1 1;有什么错? short s1 1; s1 1;有什么错?简述&&与&的区别&#xff1f;简述break与continue、return的区别&#xff1f;Arrays类的…...

Ubuntu 23.04 安装es

在Ubuntu 23.04上安装Elasticsearch的过程可能与之前版本类似&#xff0c;以下是基于最新稳定版Elasticsearch的一般安装步骤&#xff1a; 准备工作&#xff1a; 确保系统已更新至最新版本&#xff1a; sudo apt update && sudo apt upgrade安装Java Development Kit (…...

gradle 7.0 + 配置

Maven 镜像地址的设置 原来在项目根目录的 build.gradle 中进行设置&#xff0c;但是现在里面只有plugins。 工程的build.gradle的dependencies修改为plugins&#xff0c;替代了引用原来的Gradle版本。 // Top-level build file where you can add configuration options com…...

vue3的ref和reactive对比

一&#xff0c;ref 作用: 定义一个 ref 响应式的数据语法: const xxx ref(initValue) 用法 创建一个包含响应式数据的引用对象&#xff08;reference对象&#xff0c;简称ref对象&#xff09;。 JS中操作数据&#xff1a; xxx.value 模板中读取数据: 不需要.value&#xff0…...

是否应该升级到ChatGPT 4.0?深度对比ChatGPT 3.5与4.0的差异

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

C++刷题篇——04找等值元素

一、题目 二、解题思路 1、分割后放进二维数组 2、使用map&#xff0c;key为数值&#xff0c;value为其坐标 3、遍历二维数组元素&#xff0c;再在map中找该元素对应的value值&#xff08;二维数组形式&#xff09;&#xff0c;倘若value.size为1&#xff0c;那直接返回-1&…...

2024年最新服装erp软件排名!(建议收藏)

随着数字经济时代的到来&#xff0c;传统服装生产企业正在经历深刻的变革。如何实现产业数字化升级&#xff0c;是众多服装企业面临的共同课题。当前&#xff0c;服装类的企业管理软件已经成为企业实现智能化转型的关键。面对已经发生深刻改变的商业竞争环境&#xff0c;传统的…...

Radash一款JavaScript最新的实用工具库,Lodash的平替!

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

使用node爬取视频网站里《龙珠》m3u8视频

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

搜索与图论——Prim算法求最小生成树

在最小生成树问题里&#xff0c;正边和负边都没问题 朴素版prim算法 时间复杂度O(n^2) 生成树&#xff1a;每一次选中的t点&#xff0c;它和集合的距离对应的那条边&#xff0c;就是生成树的一条边 算法流程和dijkstra算法非常相似 #include<iostream> #include<cs…...

sqlmap基础知识

一、sqlmap简介 sqlmap是一个开源的渗透测试工具&#xff0c;可以自动检测和利用SQL注入漏洞以及接管数据库服务器的过程。 官网&#xff1a; sqlmap.org 核心功能 漏洞检测漏洞利用 学习关键点 基于sqlmap进行sql注入漏洞的检测&#xff0c;注入利用和攻击基于sqlmap进…...

读《C Primer Plus》

1、汇编语言是为特殊的中央处理单元设计的一系列内部指令&#xff0c;使用助记符来表示&#xff1b;不同的CPU系列使用不同的汇编语言。 2、C语言充分利用计算机优势&#xff0c;使它具有汇编语言才有的微调控能力&#xff0c;可移植性极好。 3、C语言可以访问硬件、操作内存…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...