wordpress手機(jī)號(hào)網(wǎng)站企業(yè)seo培訓(xùn)
動(dòng)態(tài)規(guī)劃—96. 不同的二叉搜索樹
- 題目描述
- 前言
- 基本思路
- 1. 問題定義
- 2. 理解問題和遞推關(guān)系
- 二叉搜索樹的性質(zhì):
- 核心思路:
- 狀態(tài)定義:
- 狀態(tài)轉(zhuǎn)移方程:
- 邊界條件:
- 3. 解決方法
- 動(dòng)態(tài)規(guī)劃方法:
- 偽代碼:
- 4. 進(jìn)一步優(yōu)化
- 5. 小總結(jié)
- Python代碼
- Python代碼解釋
- C++代碼
- C++代碼解釋
- 總結(jié)
題目描述
前言
不同的二叉搜索樹問題 是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問題。給定一個(gè)整數(shù) n
,我們需要構(gòu)造出由 n
個(gè)節(jié)點(diǎn)組成的所有不同的 二叉搜索樹(BST)。在這類問題中,我們不僅需要理解二叉搜索樹的性質(zhì),還需要通過動(dòng)態(tài)規(guī)劃來計(jì)算不同形態(tài)的二叉搜索樹的數(shù)量。
基本思路
1. 問題定義
給定一個(gè)整數(shù) n
,求由 n
個(gè)節(jié)點(diǎn)構(gòu)成的所有不同的二叉搜索樹的數(shù)量。每個(gè)二叉搜索樹的節(jié)點(diǎn)包含從 1
到 n
的整數(shù),每個(gè)整數(shù)只能使用一次。
2. 理解問題和遞推關(guān)系
二叉搜索樹的性質(zhì):
- 二叉搜索樹(BST)的性質(zhì)是,對(duì)于每個(gè)節(jié)點(diǎn):
- 左子樹上所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值。
- 右子樹上所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。
核心思路:
如果我們選擇節(jié)點(diǎn) i
作為根節(jié)點(diǎn),那么:
- 節(jié)點(diǎn)
1
到i-1
會(huì)組成根節(jié)點(diǎn)i
的左子樹。 - 節(jié)點(diǎn)
i+1
到n
會(huì)組成根節(jié)點(diǎn)i
的右子樹。 - 左子樹和右子樹的組合方式可以遞歸地進(jìn)行計(jì)算,最終組合成完整的 BST。
狀態(tài)定義:
設(shè) dp[i]
表示 i
個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量。最終我們要求解的是 dp[n]
。
狀態(tài)轉(zhuǎn)移方程:
對(duì)于每一個(gè)根節(jié)點(diǎn) i
,它的左子樹有 i-1
個(gè)節(jié)點(diǎn),右子樹有 n-i
個(gè)節(jié)點(diǎn)。左子樹和右子樹的組合方式相乘,即:
d p [ i ] = ∑ k = 1 i d p [ k ? 1 ] × d p [ i ? k ] dp[i] = \sum_{k=1}^{i} dp[k-1] \times dp[i-k] dp[i]=k=1∑i?dp[k?1]×dp[i?k]
其中,dp[k-1]
表示左子樹的組合數(shù),dp[i-k]
表示右子樹的組合數(shù)。
邊界條件:
- 當(dāng)
n = 0
時(shí),空樹也是一種二叉搜索樹,因此dp[0] = 1
。
3. 解決方法
動(dòng)態(tài)規(guī)劃方法:
- 初始化一個(gè)數(shù)組
dp
,其中dp[0] = 1
,表示空樹。 - 使用遞推公式計(jì)算
dp[i]
,即根據(jù)左子樹和右子樹的組合方式來更新dp
數(shù)組。 - 最終
dp[n]
即為n
個(gè)節(jié)點(diǎn)構(gòu)成的不同二叉搜索樹的數(shù)量。
偽代碼:
initialize dp array with dp[0] = 1
for i from 1 to n:for j from 1 to i:dp[i] += dp[j-1] * dp[i-j]
return dp[n]
4. 進(jìn)一步優(yōu)化
- 空間優(yōu)化:由于每個(gè)
dp[i]
只依賴于之前的狀態(tài),因此我們已經(jīng)使用最小的空間來存儲(chǔ)這些狀態(tài)。 - 時(shí)間復(fù)雜度:動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為
O(n^2)
,適合處理中等規(guī)模的輸入。
5. 小總結(jié)
- 問題思路:通過遞歸地構(gòu)建左子樹和右子樹,利用動(dòng)態(tài)規(guī)劃的思想,可以高效計(jì)算不同二叉搜索樹的數(shù)量。
- 核心公式:狀態(tài)轉(zhuǎn)移方程
dp[i] = \sum_{k=1}^{i} dp[k-1] \times dp[i-k]
,每次通過左子樹和右子樹的組合方式進(jìn)行計(jì)算。
以上就是不同的二叉搜索樹問題的基本思路。
Python代碼
class Solution:def numTrees(self, n: int) -> int:# 初始化dp數(shù)組,dp[i]表示i個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量dp = [0] * (n + 1)dp[0] = 1 # 空樹也是一種二叉搜索樹# 動(dòng)態(tài)規(guī)劃計(jì)算每個(gè)dp[i]的值for i in range(1, n + 1):for j in range(1, i + 1):dp[i] += dp[j - 1] * dp[i - j]return dp[n] # 返回n個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量
Python代碼解釋
- 初始化:定義一個(gè)
dp
數(shù)組,dp[i]
表示i
個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量。初始值dp[0] = 1
,表示空樹。 - 動(dòng)態(tài)規(guī)劃遞推:使用狀態(tài)轉(zhuǎn)移公式更新
dp
數(shù)組,每次根據(jù)左子樹和右子樹的組合方式來累加。 - 返回結(jié)果:返回
dp[n]
,即n
個(gè)節(jié)點(diǎn)可以構(gòu)成的不同二叉搜索樹的數(shù)量。
C++代碼
class Solution {
public:int numTrees(int n) {// 初始化dp數(shù)組,dp[i]表示i個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量vector<int> dp(n + 1, 0);dp[0] = 1; // 空樹也是一種二叉搜索樹// 動(dòng)態(tài)規(guī)劃計(jì)算每個(gè)dp[i]的值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]; // 返回n個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量}
};
C++代碼解釋
- 初始化:定義一個(gè)
dp
數(shù)組,dp[i]
表示i
個(gè)節(jié)點(diǎn)能構(gòu)成的不同二叉搜索樹的數(shù)量。初始值dp[0] = 1
,表示空樹。 - 動(dòng)態(tài)規(guī)劃遞推:使用狀態(tài)轉(zhuǎn)移公式更新
dp
數(shù)組,每次根據(jù)左子樹和右子樹的組合方式來累加。 - 返回結(jié)果:返回
dp[n]
,即n
個(gè)節(jié)點(diǎn)可以構(gòu)成的不同二叉搜索樹的數(shù)量。
總結(jié)
- 核心思路:通過遞歸構(gòu)建不同的左子樹和右子樹,利用動(dòng)態(tài)規(guī)劃求解不同二叉搜索樹的數(shù)量。每一個(gè)根節(jié)點(diǎn)的左子樹和右子樹的組合數(shù)相乘即為該根節(jié)點(diǎn)對(duì)應(yīng)的不同二叉搜索樹的數(shù)量。
- 時(shí)間復(fù)雜度:時(shí)間復(fù)雜度為
O(n^2)
,適合處理中等規(guī)模的輸入。 - 動(dòng)態(tài)規(guī)劃應(yīng)用:該問題展示了動(dòng)態(tài)規(guī)劃在樹形結(jié)構(gòu)問題中的應(yīng)用,通過遞推和組合的方式有效解決了求解二叉搜索樹數(shù)量的問題。