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

【动态规划算法题记录】343. 整数拆分 | 96.不同的二叉搜索树

整数拆分

题目🔗

题目描述

给定一个正整数 n ,将其拆分为 k个正整数的和(k >= 2),并使这些整数的乘积最大化。

返回你可以获得的最大乘积

思路分析

  1. dp数组含义dp[i]表示整数i拆分后的最大乘积。
  2. 递推公式dp[i] = j * dp[i - j]
  3. dp数组初始化dp[0] = 0, dp[1] = 0, dp[2] = 1

cpp代码

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[0] = 0;dp[1] = 0;dp[2] = 1;for(int i = 3; i <= n; ++i){for(int j = 1; j <= i/2; ++j){dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};

不同的二叉搜索树

题目🔗

题目描述

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

思路分析

在这里插入图片描述

  1. dp数组含义dp[i]表示由i个节点组成的不同二叉搜索树的数量。
  2. 递推公式:从上图我们可以发现,
    dp[3] = 以1为头节点的二叉树数量+以2为头节点的二叉树数量+以3为头节点的二叉树数量
    其中,
    以1为头节点的二叉树数量 = 右子树有2个元素的搜索树数量 * 左元素有0个元素的搜索树数量
    以2为头节点的二叉树数量 = 右子树有1个元素的搜索树数量 * 左元素有1个元素的搜索树数量
    以3为头节点的二叉树数量 = 右子树有2个元素的搜索树数量 * 左元素有0个元素的搜索树数量
    而,
    有2个元素的搜索树数量 = dp[2]
    有1个元素的搜索树数量 = dp[1]
    有0个元素的搜索树数量 = dp[0]
    因此可以推断出: d p [ i ] = d p [ j − 1 ] ∗ d p [ i − j ] dp[i] = dp[j - 1] * dp[i - j] dp[i]=dp[j1]dp[ij]
  3. dp数组初始化dp[0] = 1

cpp代码

class Solution {
public:int numTrees(int n) {vector<int> dp(n+1);dp[0] = 1;for(int i = 1; i <= n; ++i){for(int j = 1; j <= i; ++j){dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
};

总结

这两题都是属于思路比较绕,但想清楚之后会发现很简单的,所以前期一定要理解dp数组的相关含义。

相关文章:

【动态规划算法题记录】343. 整数拆分 | 96.不同的二叉搜索树

整数拆分 题目&#x1f517; 题目描述 给定一个正整数 n &#xff0c;将其拆分为 k个正整数的和&#xff08;k > 2&#xff09;&#xff0c;并使这些整数的乘积最大化。 返回你可以获得的最大乘积 。 思路分析 dp数组含义&#xff1a;dp[i]表示整数i拆分后的最大乘积。…...

网页上预览Excel文件

如何运行: 需要发布在服务器 如Tomcat 实例图片: 需要展示的文件: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>excel预览</title><link rel"stylesheet" href"…...

Unity射击游戏开发教程:(31)制造一定追踪行为的敌人

在本文中,我们将介绍如何在两种敌人行为之间切换。本文是前两篇文章的延续,分别介绍了敌人躲避玩家射击以及敌人不断旋转并向玩家射击的情况。我只是介绍如何在这两种行为之间进行转换。 这种新的敌人行为的目标: 当不开火时,敌人可以躲避玩家的射击。射击时,敌人无法躲避…...

springboot mybatis plus 固定查询条件及可选查询条件的组合查询,使用QueryWrapper.and()来解决。

1、我们在写查询SQL的时候&#xff0c;经常会碰到&#xff0c;比如&#xff0c;同一个类别下的某一个编号的物料信息&#xff0c;或者是同一批次的物料库存问题等等。 所属类别fid物料编号bm物料批次pc110.01.0220240807110.01.0320240807 210.02.0120240805 2、那么我…...

使用ollama取代openai的api进行graphRAG失败记录

pip install ollama pip install langchain_ollama graph_documents llm_transformer.convert_to_graph_documents(split_documents) print(graph_documents) 偶尔会成功&#xff0c;但是大部分是失败的&#xff1a; 报错记录如下&#xff0c;暂时没想到好的办法&#xff…...

MyBatis 配置与测试方式

目录 一&#xff0c;什么是MyBatis 二&#xff0c;准备工作 创建项目 配置数据库连接 持久层代码 单元测试 一&#xff0c;什么是MyBatis 简单来说&#xff0c;MyBatis 是一款优秀的持久层框架&#xff0c;用于简化JDBC的开发&#xff0c;能更简单完成程序与数据库之间…...

C#实现代理服务器

在C#中实现一个简单的代理服务器&#xff0c;可以使用System.Net.Sockets命名空间下的TcpListener类来监听客户端的连接请求&#xff0c;并使用TcpClient来处理与客户端的通信。以下是一个简单的代理服务器示例&#xff1a; using System; using System.IO; using System.Net;…...

react的路由实战使用

环境配置&#xff1a;vitetsreact18 1、安装包 npm i react-router-dom 2、 根路由配置以及路由挂载 a、在src下面创建router文件夹配置简单的路由信息&#xff1a; router/index.tsx import { createBrowserRouter } from "react-router-dom"; import UserLogin…...

python 字典转成类 构建类

目录 python 字典转成类 复杂嵌套示例: 动态实例化类 太好用了! python 字典转成类 class DictToClass:def __init__(self, dictionary):for key, value in dictionary.items():if isinstance(value, dict):# 如果值是字典,递归转换为类的实例setattr(self, key, DictToC…...

springboot 过滤器

1、过滤器的实现 springboot中过滤器通过实现接口Filter并重写init、doFilter、destroy三个方法。在三个方法中加入自己的业务逻辑处理。 【注意】Filter接口的完整包名在不同的jdk版中中的变化。这里示例中使用的版本为 open-jdk17。完整名称 jakarta.servlet.Filter。如果使…...

【C语言篇】深入理解指针1

文章目录 内存和地址内存编址 指针变量和地址取地址操作符指针变量和解引用操作符指针变量指针变量类型解引用操作符指针变量的大小 指针变量类型的意义指针的解引用指针-整数void*指针 const修饰指针指针运算指针-整数指针-指针指针的关系运算 野指针野指针成因如何规避野指针…...

IAP程序升级 与 电脑BIOS 的关系

IAP (In-Application Programming) 程序升级 IAP程序升级是一种技术&#xff0c;允许设备在运行过程中更新其自身的固件或软件&#xff0c;而不需要外部工具或设备的介入。这种技术特别适用于嵌入式系统和物联网&#xff08;IoT&#xff09;设备。其主要由三部分构成&#xff0…...

Java使用MQTT协议

MQTT&#xff08;Message Queuing Telemetry Transport&#xff0c;消息队列遥测传输协议&#xff09;是一种轻量级的、基于发布/订阅模式的物联网通信协议。它构建于TCP/IP协议之上&#xff0c;由IBM在1999年发布。MQTT的主要特点包括&#xff1a; 轻量级与高效&#xff1a;M…...

等级+时间的优先级算法

简介 本算法为等级与时间结合计算对应优先级逻辑 等级越高者优先级越高 同等级下&#xff0c;时间越小者优先级越高 实现 主方法 calculatePriority import com.zk.blog.enums.TypeEnum; import org.apache.commons.lang3.StringUtils;/*** program: * description:* autho…...

物流仓库安全视频智能管理方案:构建全方位、高效能的防护体系

一、背景分析 随着物流行业的快速发展和仓储需求的日益增长&#xff0c;仓库安全成为企业运营中不可忽视的重要环节。传统的人工监控方式不仅效率低下&#xff0c;且难以做到全天候、无死角覆盖&#xff0c;给仓库资产和人员安全带来潜在风险。因此&#xff0c;引入仓库安全视…...

jackson反序列化漏洞

jackson反序列化漏洞 反序列化漏洞触发根因jackson介绍jackson反序列化漏洞关键点enableDefaultTypingactivateDefaultTypingJsonTypeInfo 漏洞触发场景漏洞复现环境引入依赖pocactivateDefaultTypingenableDefaultTypingJsonTypeInfo 参考 很久没写blog&#xff0c;最近慢慢开…...

Java | Leetcode Java题解之第328题奇偶链表

题目&#xff1a; 题解&#xff1a; class Solution {public ListNode oddEvenList(ListNode head) {if (head null) {return head;}ListNode evenHead head.next;ListNode odd head, even evenHead;while (even ! null && even.next ! null) {odd.next even.nex…...

100 Exercises To Learn Rust 挑战!准备篇

公司内部的学习会非常活跃&#xff01;我也参与了Rust学习会&#xff0c;并且一直在研究rustlings。最近&#xff0c;我发现了一个类似于rustlings的新教程网站&#xff1a;Welcome - 100 Exercises To Learn Rust。 rustlings是基于Rust的权威官方文档《The Rust Programming…...

瑞_RabbitMQ_初识MQ

文章目录 1 初识MQ1.1 同步调用1.1.1 同步调用的优势1.1.2 同步调用的缺点 1.2 异步调用1.2.1 异步调用的角色1.2.2 异步调用的优势1.2.3 异步调用的缺点1.2.4 异步调用的场景 1.3 MQ技术选型 2 RabbitMQ2.1 安装2.1.1 资源准备2.1.2 安装步骤 2.2 RabbitMQ架构2.3 RabbitMQ管理…...

系统内存管理:虚拟内存、内存分段与分页、页表缓存TLB以及Linux内存管理

虚拟内存 虚拟内存是一种操作系统提供的机制&#xff0c;用于将每个进程分配的独立的虚拟地址空间映射到实际的物理内存地址空间上。通过使用虚拟内存&#xff0c;操作系统可以有效地解决多个应用程序直接操作物理内存可能引发的冲突问题。 在使用虚拟内存的情况下&#xff0…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...