【力扣】96. 不同的二叉搜索树 <动态规划>
【力扣】96. 不同的二叉搜索树
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3
输出:5
示例 2:
输入:n = 1
输出:1
提示:
1 <= n <= 19
题解
- 确定 dp 数组以及下标的含义
dp[i] : 1到 i 为节点组成的二叉搜索树的个数为 dp[i]
i 个不同元素节点组成的二叉搜索树的个数为 dp[i] - 确定递推公式
dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是 dp[2]。有1个元素的搜索树数量就是 dp[1]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
dp[i] += dp[以 1到i-1 为头结点左子树节点数量] * dp[以 i-(1到i-1) 为头结点右子树节点数量]
所以递推公式:dp[i] += dp[j - 1] * dp[i - j]
; ,j-1 为 j 为头结点左子树节点数量,i-j 为以 j 为头结点右子树节点数量。
- dp 数组如何初始化
dp[0] = 1 - 确定遍历顺序
节点数为 i 的状态是依靠 i 之前节点数的状态。
那么遍历 i 里面每一个数作为头结点的状态,用 j 来遍历
for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}
}
- 举例推导 dp 数组(打印 dp 数组)
class Solution {public int numTrees(int n) {//初始化int[] dp = new int[n + 1];//初始化0个节点和1个节点的情况dp[0] = 1;// 遍历for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {// dp 方程dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
}
相关文章:

【力扣】96. 不同的二叉搜索树 <动态规划>
【力扣】96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n 3 输出:5 示例 2: 输入&am…...

Win11搭建 Elasticsearch 7 集群(一)
一: ES与JDK版本匹配一览表 elasticsearch从7.0开始默认安装了java运行环境,以便在没有安装java运行环境的机器上运行。如果配置了环境变量JAVA_HOME,则elasticsearh启动时会使用JAVA_HOME作为java路径,否则使用elasticsearch根目…...

哭了,python自动化办公,终于支持 Mac下载了
想了解更多精彩内容,快来关注程序员晚枫 大家好,这里是程序员晚枫,小红薯/小破站也叫这个名。 在我的主页发布的免费课程:给小白的《50讲Python自动化办公》,一直在更新中,昨晚12点多,有朋友在…...

【已更新建模代码】2023数学建模国赛B题matlab代码--多波束测线问题
一、 问题重述 1.1问题背景 海洋测深是测定水体深度与海底地形的重要任务,有两种主要技术:单波束测 深与多波束测深。单波束适用于简单任务,但多波束可提供更精确的地形数据。多 波束系统的关键在于覆盖宽度与重叠率的设计,以确保…...

GMSL技术让汽车数据传输更为高效(转)
目前,大部分车企都在其旗舰车型上配备了达到Level 2水平的自动驾驶技术,也就是高级自动驾驶辅助 ADAS系统。ADAS系统硬件主要由以下几部分组成,包括传感器、串行器、解串器、ADAS处理器等。 除了ADAS系统,包括传感器融合、音视频影…...

ARM+Codesys标准通用型控制器
整机工业级设计,通讯外设经过隔离保护 电源宽电压设计(9~36V DC ) 丰富的通讯接口,满足多种场合控制和通讯需求 四核工业级处理器,高性能,低功耗,高可靠性 机身无风扇设计,外壳小巧 搭载内核 100% 自主…...

YOLOV8从零搭建一套目标检测系统(修改model结构必看)附一份工业缺陷检测数据集
目录 1.YOLOV8介绍 2.YOLOV8安装 2.1环境配置 3.数据集准备 1.YOLOV8介绍 Yolov8结构图: YoloV8相对于YoloV5的改进点: Replace the C3 module with the C2f module. Replace the first 6x6 Conv with 3x3 Conv in the Backbone. Delete two Convs …...
Maven 的其它插件
文章目录 Maven 的其它插件dockerfile 插件Apache Maven Checkstyle Pluginp3c-pmd Maven 的其它插件 dockerfile 插件 dockerfile-maven-plugin 是 spotify 公司新提供的、用以替代 docker-maven-plugin 的插件,它同样是用于在 maven 中将当前项目打成一个 docke…...
系列十三、Java操作RocketMQ之带Key的消息
一、概述 RocketMQ中的消息,默认会有一个messageId当做消息的唯一标识,我们也可以给消息携带一个key,用作唯一标识或者业务标识,包括在控制面板(Dashboard,RocketMQ的一个可视化面板)中也可以使…...
C#调用Dapper
1-查询数据 string sql “查询语句”; using (SqlConnection con new SqlConnection(数据库连接信息)) { List<表结构实体类> list con.Query<表结构实体类>(sql).ToList(); } 2-执行sql string sql “UPDATE table1 SET column1 Name where id id”; using…...

2023高教杯数学建模1:ABC题目+初步想法
2023 ABC题目初步想法 写在最前面A题:定日镜场的优化设计问题1:建模将其抽象为数学公式问题2:固定部分参数,约束条件下的局部最优化问题可尝试方法 问题3:约束条件下的局部最优化问题附录:相关计算公式参考…...

ApachePulsar原理解析与应用实践(学习笔记一)
随着时代的发展,软件设计的理念也在不断发展,从单体服务、面向服务、微服务,发展到云原生以及无服务。其演变的过程是一个能力不断增强,领域边界不断微分细化的过程。比如无服务就是将函数作为服务,就类似dns模式的服务…...

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书南京财经大学图书馆
2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书南京财经大学图书馆...
qt 信号与槽机制,登录界面跳转
登录界面跳转 配置文件 .pro QT core gui texttospeechgreaterThan(QT_MAJOR_VERSION, 4): QT widgetsCONFIG c11# The following define makes your compiler emit warnings if you use # any Qt feature that has been marked deprecated (the exact warnings # d…...
uniapp的两个跳转方式
uniapp内置多种跳转方式,我这里介绍两个最常用的跳转,uni.navigateTo和uni.switchTab,前者为跳转到非TabBar页面,后者为跳转到TabBar页面,所谓TabBar就是底部导航栏配置的页面,例如下方的index.vue。 在pa…...

【LeetCode】1654:到家的最少跳跃次数的解题思路 关于力扣无法return的BUG的讨论
文章目录 一、题目二、题解与代码三、神奇的BUG3.1 无法执行的 return 和 break 语句3.2 通过另一个 break 解决 一、题目 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发,到达它的家。 跳蚤跳跃的规则如下: 它可以 往前 跳恰好 a 个位…...

Calico IP In IP模拟组网
Calico IP In IP模拟组网 网络架构 模拟组网 先在k8s-master-1节点执行如下命令: # 创建veth-pair设备对ip link add veth1 type veth peer name eth0# 创建ns1网络命名空间ip netns add ns1# 将eth0网卡插入ns1网络命名空间ip link set eth0 netns ns1# 为ns1网…...

在linux上挂载windows共享目录
挂载要求 非root用户(普通用户)能够读写windows共享目录,比如查看文件、创建文件、修改文件、删除文件 # 让普通用户也可以正常读写 uidvalue and gidvalue Set the owner and group of the root of the file system (default: uidgid0, bu…...

drone的简单使用
(一)简介 Drone 是一个基于Docker容器技术的可扩展的持续集成引擎,用于自动化测试、构建、发布。每个构建都在一个临时的Docker容器中执行,使开发人员能够完全控制其构建环境并保证隔离。开发者只需在项目中包含 .drone.yml文件&…...
day 52 | 84.柱状图中最大的矩形
84.柱状图中最大的矩形 本题跟接雨水的思路是差不多的,不同的是接雨水找到的凹,这个找的是凸。因此是找到左右第一个比他小的值。因此单调栈中的顺序是从栈头到栈尾单调增。 需要注意的是,为了防止给定的元素是单调增或者单调减,…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...