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

leetcode 不同的二叉搜索树

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

示例 1:

输入:n = 3
输出:5
示例 2:

输入:n = 1
输出:1

采用dp[i] 表示含有i个节点的二叉搜索树,其中二叉搜索树由左子树和右子树以及根结点组成。其中dp[i]由含有i-j节点的左子树和j-1节点的右子树和一个根结点组成。所以dp[i]的构造形式由左右子树决定。

最优子结构 dp[i]

状态转移方程:dp[i] += (dp[i - j] * dp[j - 1])

int numTrees(int n) {
    int dp[20] = {0};
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i] += (dp[i - j] * dp[j - 1]);
        }
    }
    return dp[n];
}
原文地址:https://blog.csdn.net/qq_43309286/article/details/134632080
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/146772.html

相关文章:

  • ES6语法
  • Vue基础(2)
  • 第18个项目:微信开发入门:获取access_token的Python源码
  • 数据结构——算法基础
  • Picsart美易照片编辑器和视频编辑器
  • stm32单片机个人学习笔记14(USART串口数据包)
  • java基础-运算符
  • virtualList 封装使用 虚拟列表 列表优化
  • 第四节HarmonyOS 熟知开发工具DevEco Studio
  • 深入解析:如何开发抖音票务小程序
  • CANdelaStudio 中 Bese Variant 和 Variant区别
  • JavaScript WebApi(二) 详解
  • Redis 命令处理过程
  • SIPp mac和debian用法可能略有差别
  • 【数据中台】开源项目(2)-Wormhole流式处理平台
  • 【0239】从编译原理角度理解 #include “xxx“ 或 #include<xxx> 的实现机制
  • 部署jekins遇到的问题
  • 初识Spring (Spring 核心与设计思想)
  • WEB渗透—反序列化(七)
  • 大数据-之LibrA数据库系统告警处理(ALM-37004 Datanode主备不同步或者断连)
  • CGAN原理讲解与源码
  • 机器人分类
  • zi定义指令
  • 【jvm】虚拟机之堆
  • Unity 场景切换
  • 【Java数据结构 -- 包装类和泛型】