【力扣】96. 不同的二叉搜索树 <动态规划>

这篇具有很好参考价值的文章主要介绍了【力扣】96. 不同的二叉搜索树 <动态规划>。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【力扣】96. 不同的二叉搜索树

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

示例 1:
【力扣】96. 不同的二叉搜索树 <动态规划>,力扣及OJ,# 动态规划,动态规划,leetcode,算法
输入: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]
    【力扣】96. 不同的二叉搜索树 <动态规划>,力扣及OJ,# 动态规划,动态规划,leetcode,算法

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 为头结点右子树节点数量。文章来源地址https://www.toymoban.com/news/detail-690392.html

  • 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. 不同的二叉搜索树 <动态规划>的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode题目详解】第九章 动态规划part03 343. 整数拆分 96.不同的二叉搜索树 (day41补)

    给定一个正整数  n  ,将其拆分为 k 个 正整数 的和(  k = 2  ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 看到这道题目,都会想拆成两个呢,还是三个呢,还是四个.... 我们来看一下如何使用动规来解决。 # 动态规划 动

    2024年02月10日
    浏览(46)
  • 算法刷刷刷|动态规划篇|509.斐波那契数| 70.爬楼梯| 746.使用最小花费爬楼梯| 62.不同路径| 63不同路径2| 343.正数拆分 | 96.不同的二叉搜索树

    509. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 70.爬楼梯 746.使用最小花费爬楼梯 给你一个整数

    2023年04月23日
    浏览(57)
  • 96. 不同的二叉搜索树

    目录 1、题目描述 2、思路:动态规划 2.2、确定递推公式 2.3、dp数组初始化 2.4、确定遍历顺序 3、C++实现如下 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3 输出:5 示例

    2024年02月02日
    浏览(69)
  • leetcode做题笔记96. 不同的二叉搜索树

    给你一个整数  n  ,求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种?返回满足题意的二叉搜索树的种数。 本题与上题近似,只需分别考虑左右子树,即f[j-1]*f[i-j]得到状态方程,最后输出f[n[即可,或者直接使用公式,二叉搜索树的种数与

    2024年02月11日
    浏览(37)
  • 【动态规划 NK刷题记 DP5 之 有多少个不同的二叉搜索树

    目录  一、题解部分 1.1题目 1.2铺垫 1.3.题解: 二、法一:递归实现 1.输入数据,创建动态数组  2.断言dp指针,并给它赋值 3.打印结果并调用函数 3.1注意: 4.实现函数binarytree 4.1先将动态数组dp[i]中特殊的值给出来,比如i=1,i=0时 4.2然后循环遍历节点的数量为i时,根节点j的

    2024年02月07日
    浏览(62)
  • 算法训练第四十一天|343. 整数拆分 、96.不同的二叉搜索树

    题目链接:343. 整数拆分 参考:https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html 题目描述 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入:

    2023年04月24日
    浏览(44)
  • java数据结构与算法刷题-----LeetCode96. 不同的二叉搜索树

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只

    2024年01月21日
    浏览(56)
  • LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

    题目 :给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保

    2023年04月19日
    浏览(69)
  • leetcode做题笔记95. 不同的二叉搜索树 II

    给你一个整数  n  ,请你生成并返回所有由  n  个节点组成且节点值从  1  到  n  互不相同的不同  二叉搜索树   。可以按  任意顺序  返回答案。 本题要列出所有二叉搜索树,即可转换为列举左子树所有集合和右子树所有集合两个问题,分别用递归函数将左右子树根节

    2024年02月11日
    浏览(33)
  • 【力扣】62. 不同路径 <动态规划>

    一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7 输出:28 示例 2: 输入:m

    2024年02月10日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包