iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 27
1
Software Development

從LeetCode學演算法系列 第 27

[Day 27] 從LeetCode學演算法 - 0096. Unique Binary Search Trees (Medium)

目標:
這題主要目的在於再進一步引導讀者去思考如何做出一個適合dp的鏈結關係。

原題:

Question:
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
   1         3       3         2       1
    \        /      /         / \       \
     3     2       1         1   3       2
    /     /         \                     \
   2     1           2                     3

分析/解題:
還記得什麼是二元搜尋樹嗎?
不知道的話,可以翻閱前面的Day 17的介紹歐!
簡言之,一個合法的BST除了左邊的節點要全小於根節點,
右邊的節點要全大於根節點
外,其左右子樹也要是BST才行。
觀察n=3的狀況,我們可以將其歸納成3類:
以1為根節點/以2為根節點/以3為根節點。

首先是1為根節點的狀況:
左邊沒有比其小的節點,故只有一種可能;
右邊有2跟3的組合,相當於n=2的時候的狀況(2種)。
(2跟3等價於1跟2兩個節點會有的組合)

再來是2為根節點的狀況:
左邊只有1種可能(1這個節點);
右邊也只有1種可能(3這個節點)。

最後是3為根節點的狀況:
左邊是1跟2的組合(2種),
右邊只有1種可能。

如果我們將n的組合命名為函式f(n),
那麼顯然f(0)=1(只有一種可能),f(1)=1。

計算n=3的組合算法為:
f(0) * f(2) + f(1) * f(1) + f(2) * f(0)

掌握這個規律的狀態,我們可以得到f(n)的計算方式:
f(0) * f(n-1) + f(1) * f(n-2) + … + f(n-1) * f(0)
那麼,從f(1)開始起算的話,
我們可以一路疊加將f(1)到f(n-1)都算出來,
最後得到我們要的f(n)。
讓f(n)能夠化成f(n-1)或較小的項次的組合,一路化簡到能直接確認的值,
所以這個就是典型的動態規劃的範例。

Java:

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

Python:

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1):
            for j in range(0, i):
                dp[i] += dp[j] * dp[i - j - 1]
            
        return dp[n]

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(n²), O(n)
由於計算時兩層迴圈最大都要經歷n,故時間上會和n的平方相關)

「可以改成遞迴的方式嗎?」
(可以,我們只要將dp改成字典或HashMap,開一個函式search,
令其在找不到值的時候呼叫自己如 sum += search(i-1) * search(n-i),
最後也會如同迴圈的解法一樣一路拆解到最底下,
讀者可以自行嘗試看看,實測上兩者速度在實作正確的狀況下,
應該是感受不出太明顯的差異的。)

此外,本文的解其實等同於Catalan number,讀者可參考閱讀。

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0189. Rotate Array (Easy)


上一篇
[Day 26] 從LeetCode學演算法 - 0283. Move Zeroes (Easy)
下一篇
[Day 28] 從LeetCode學演算法 - 0189. Rotate Array (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言