DP入门之差异的二叉征采树!

发布日期:2022-08-06 20:27    点击次数:138
差异的二叉征采树

标题成就成就链接:https://leetcode-cn.com/problems/unique-binary-search-trees

给定一个整数 n,求以 1 ... n 为节点形成的二叉征采树有几多种?

示例:

思路

这道标题成就成就形貌很烦复,但估量大部份同砚看完都是懵懵的形态,这得怎么统计呢?

对付什么是二叉征采树,我们从前在解说二叉树专题的时光已经详细解说过了,也可以看看这篇二叉树:二叉征采树退场!再追念一奔忙。

相识了二叉征采树当前,我们该领先举几个例子,画画图,看看有无什么纪律,如图:

差异的二叉征采树

n为1的时光有一棵树,n为2有两棵树,这个是很直观的。

差异的二叉征采树1

来看看n为3的时光,有哪几种环境。

当1为头结点的时光,其右子树有两个节点,看这两个节点的计划,是否是和 n 为2的时光两棵树的计划是同样的啊!

(可以或许有同砚识了,这计划不一样啊,节点数值都不一样。别忘了我们就是求差异树的数量,着实不消把征采树都列进去,所以不消体贴其详细数值的差异)

当3为头结点的时光,其左子树有两个节点,看这两个节点的计划,是否是和n为2的时光两棵树的计划也是同样的啊!

当2为头结点的时光,其阁下子树都只要一个节点,计划是否是和n为1的时光只要一棵树的计划也是同样的啊!

缔造到这里,着实我们就找到了重叠子成就了,着实也就是缔造可以或许经由过程dp[1] 和 dp[2] 来推导进去dp[3]的某种编制。

思虑到这里,这道标题成就成就就有眉目了。

dp[3],就是 元素1为头结点征采树的数量 + 元素2为头结点征采树的数量 + 元素3为头结点征采树的数量

元素1为头结点征采树的数量 = 右子树有2个元素的征采树数量 * 左子树有0个元素的征采树数量

元素2为头结点征采树的数量 = 右子树有1个元素的征采树数量 * 左子树有1个元素的征采树数量

元素3为头结点征采树的数量 = 右子树有0个元素的征采树数量 * 左子树有2个元素的征采树数量

有2个元素的征采树数量就是dp[2]。

有1个元素的征采树数量就是dp[1]。

有0个元素的征采树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

如图所示:

差异的二叉征采树2

此时我们已经找到递推纠葛了,那末可以或许用动规五部曲再体系阐发一遍。

1.肯定dp数组(dp table)以及下标的含义

dp[i] :1到i为节点形成的二叉征采树的个数为dp[i]。

也可以理解是i的差异元素节点形成的二叉征采树的个数为dp[i] ,都是同样的。

下列阐发假定想不清楚,就来回首一下dp[i]的定义

2.肯定递推公式

在上面的阐发中,着实已经看出其递推纠葛, dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当是以头结点的元素,从1遍历到i为止。

所以递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量

3.dp数组怎么初始化

初始化,只需求初始化dp[0]就能了,推导的根抵,都是dp[0]。

那末dp[0]该当是几多呢?

从定义下去讲,产品中心空节点也是一棵二叉树,也是一棵二叉征采树,这是可以或许说得通的。

从递归公式下去讲,dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0,也需求dp[以j为头结点左子树节点数量] = 1, 否则乘法的终局就都变成0了。

所以初始化dp[0] = 1

4.肯定遍历按次

首先必定是遍历节点数,从递归公式:dp[i] += dp[j - 1] * dp[i - j]可以或许看出,节点数为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];     } } 

5.举例推导dp数组

n为5时光的dp数组形态如图:

差异的二叉征采树3

固然假定自身画图举例的话,根抵举例到n为3就能了,n为4的时光,画图已经相比麻烦了。

我这里列到了n为5的环境,是为了方便巨匠 debug代码的时光,把dp数组打进去,看看何处有成就。

综上阐发终了,C++代码以下:

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];     } }; 
时光宏壮度: 空间宏壮度:

巨匠该当缔造白,我们阐发了这么多,最后代码却云云俭朴!

总结

这道标题成就成就诚然在力扣上标记是中等难度,但可以或许算是费力了!

首先这道题想到用动规的编制来经管,就不太好想,需求举例,画图,阐发,材干找到递推的纠葛。

尔后难点就是肯定递推公式了,假定把递推公式想清楚了,遍历按次和初始化,就是自然而然的工作了。

可以或许看出我依然照旧用动规五部曲来举行阐发,会把标题成就成就的各个方面都笼盖到!

而且详细这五部阐发是我自身寻常总结的经历,找不进去第二个的,可以或许过一阵子 别的题解也会有动规五部曲了,哈哈。

事先我在用动规五部曲解说斐奔忙那契的时光,一些录友和我反馈,感到讲宏壮了。

着实事先我一贯夸大俭朴题是用来实习编制论的,着实不克不迭因为俭朴我就代码一甩,俭朴说明一下就完事了。

可以或许事先一些同砚不睬解,今朝巨匠该当感想感染编制论的首要性了,加油??

本文转载自微信群众号「代码随想录」,可以或许经由过程下列二维码关注。转载本文请联络代码随想录群众号。