DP入門之不同的二叉搜索樹！

作者：程序員Carl 2022-01-11 10:01:25

開發(fā) 前端

關(guān)于什么是二叉搜索樹，我們之前在講解二叉樹專題的時(shí)候已經(jīng)詳細(xì)講解過了，也可以看看這篇二叉樹：二叉搜索樹登場(chǎng)!再回顧一波。

不同的二叉搜索樹

題目鏈接：https://leetcode-cn.com/problems/unique-binary-search-trees

給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種?

示例:

思路

這道題目描述很簡短，但估計(jì)大部分同學(xué)看完都是懵懵的狀態(tài)，這得怎么統(tǒng)計(jì)呢?

了解了二叉搜索樹之后，我們應(yīng)該先舉幾個(gè)例子，畫畫圖，看看有沒有什么規(guī)律，如圖：

不同的二叉搜索樹

n為1的時(shí)候有一棵樹，n為2有兩棵樹，這個(gè)是很直觀的。

不同的二叉搜索樹1

來看看n為3的時(shí)候，有哪幾種情況。

當(dāng)1為頭結(jié)點(diǎn)的時(shí)候，其右子樹有兩個(gè)節(jié)點(diǎn)，看這兩個(gè)節(jié)點(diǎn)的布局，是不是和 n 為2的時(shí)候兩棵樹的布局是一樣的啊!

(可能有同學(xué)問了，這布局不一樣啊，節(jié)點(diǎn)數(shù)值都不一樣。別忘了我們就是求不同樹的數(shù)量，并不用把搜索樹都列出來，所以不用關(guān)心其具體數(shù)值的差異)

當(dāng)3為頭結(jié)點(diǎn)的時(shí)候，其左子樹有兩個(gè)節(jié)點(diǎn)，看這兩個(gè)節(jié)點(diǎn)的布局，是不是和n為2的時(shí)候兩棵樹的布局也是一樣的啊!

當(dāng)2為頭結(jié)點(diǎn)的時(shí)候，其左右子樹都只有一個(gè)節(jié)點(diǎn)，布局是不是和n為1的時(shí)候只有一棵樹的布局也是一樣的啊!

發(fā)現(xiàn)到這里，其實(shí)我們就找到了重疊子問題了，其實(shí)也就是發(fā)現(xiàn)可以通過dp[1] 和 dp[2] 來推導(dǎo)出來dp[3]的某種方式。

思考到這里，這道題目就有眉目了。

dp[3]，就是元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量

元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有2個(gè)元素的搜索樹數(shù)量 * 左子樹有0個(gè)元素的搜索樹數(shù)量

元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有1個(gè)元素的搜索樹數(shù)量 * 左子樹有1個(gè)元素的搜索樹數(shù)量

元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有0個(gè)元素的搜索樹數(shù)量 * 左子樹有2個(gè)元素的搜索樹數(shù)量

有2個(gè)元素的搜索樹數(shù)量就是dp[2]。

有1個(gè)元素的搜索樹數(shù)量就是dp[1]。

有0個(gè)元素的搜索樹數(shù)量就是dp[0]。

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

如圖所示：

不同的二叉搜索樹2

此時(shí)我們已經(jīng)找到遞推關(guān)系了，那么可以用動(dòng)規(guī)五部曲再系統(tǒng)分析一遍。

1.確定dp數(shù)組(dp table)以及下標(biāo)的含義

dp[i] ：1到i為節(jié)點(diǎn)組成的二叉搜索樹的個(gè)數(shù)為dp[i]。

也可以理解是i的不同元素節(jié)點(diǎn)組成的二叉搜索樹的個(gè)數(shù)為dp[i] ，都是一樣的。

以下分析如果想不清楚，就來回想一下dp[i]的定義

2.確定遞推公式

在上面的分析中，其實(shí)已經(jīng)看出其遞推關(guān)系， dp[i] += dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量]

j相當(dāng)于是頭結(jié)點(diǎn)的元素，從1遍歷到i為止。

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量，i-j 為以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量

3.dp數(shù)組如何初始化

初始化，只需要初始化dp[0]就可以了，推導(dǎo)的基礎(chǔ)，都是dp[0]。

那么dp[0]應(yīng)該是多少呢?

從定義上來講，空節(jié)點(diǎn)也是一棵二叉樹，也是一棵二叉搜索樹，這是可以說得通的。

從遞歸公式上來講，dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量] 中以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量為0，也需要dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] = 1，否則乘法的結(jié)果就都變成0了。

所以初始化dp[0] = 1

4.確定遍歷順序

首先一定是遍歷節(jié)點(diǎn)數(shù)，從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節(jié)點(diǎn)數(shù)為i的狀態(tài)是依靠 i之前節(jié)點(diǎn)數(shù)的狀態(tài)。

那么遍歷i里面每一個(gè)數(shù)作為頭結(jié)點(diǎn)的狀態(tà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.舉例推導(dǎo)dp數(shù)組

n為5時(shí)候的dp數(shù)組狀態(tài)如圖：

不同的二叉搜索樹3

當(dāng)然如果自己畫圖舉例的話，基本舉例到n為3就可以了，n為4的時(shí)候，畫圖已經(jīng)比較麻煩了。

我這里列到了n為5的情況，是為了方便大家 debug代碼的時(shí)候，把dp數(shù)組打出來，看看哪里有問題。

綜上分析完畢，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]; 
    } 
};