今天是預計準備題目內容的最後一天，明天會先就目前這 30 天的內容做一個 index 版本的整理，這也是我 30 天文章的習慣，如果有人接觸系列文章想要快速找到自己需要的部分，index 這篇文章對他們和對我自己，都是一個很好的大綱總結，也會稍微寫一下自己這 30 天的小心得。

不想一篇裡面塞太多內容，所以單篇的題目選題還是維持一定數量。但 30 天結束後，我有機會可能還是會繼續更新寫到覺得有心得的題目，如果覺得這幾天以來寫的方式是你喜歡的、能讀懂的，歡迎訂閱追蹤本專欄。

Unique Binary Search Trees

題目給定一個 n 值，要求我們回傳有 n 個節點的二元搜尋樹(BST)共有幾種可能的排列方式。
這題我覺得算是相當抽象的問題，我第一次也是看解析才能夠理解其中的動態規劃思路，老實說真的不是那麼好想。
看到這個題目一開始覺得無從下手是很正常的，但希望看到這邊的人還是先想想看，自己會怎麼寫，想一下遇到的難點，比較動態規劃帶來的解法，可能會讓自己有一些豁然開朗的概念。
我自己在第一次想的時候，我很執著在數字的遞增遞減上，哪個數字該放哪邊，很著重在數字的直接對應上。

這題動態規劃的思路是這樣的，讓我們來觀察「結構」排列本身。

 1 | 1       2
   |  \     /
   |   2   1

上面是當 n 為 1 和 n 為 2 的時候有的 BST 排列方式，分別為 1 種和 2 種，至此，還看不出來太多的規律。
接著來看 n 為 3 的例子。

  1      1       2        3     3
   \      \     / \      /     /
    2      3   1   3    2     1
     \    /            /       \
      3  2            1         2

這個例子在動態規劃的視角看起來，重視的是左右子樹的排列順序。
對 BST 來說，一旦固定了 root，就決定了哪些元素能放左邊，哪些元素能放右邊，這題的動態規劃思維抓住了這點。
當 n = 3，總共有 3 種以不同 root 的排列可能，分別是 1 兩種、2 一種、3 兩種。
這邊要明確一下，當沒有節點的時候，也算一顆 BST，所以假設有 n = 0 的 case，則種類為 1。
我們關注的狀態是排列種類，讓我們嘗試把 dp[i] 定義為有 i 個節點時的排列數量，其中 i 必須 >= 3，小於的情況我們用個案處理。

在我們確立根節點後，假設左邊有 x 種排列方法，右邊有 y 種排列方法，則對於此根結點，總共的排列方法應該是 x 乘上 y(排列的概念，左加右加根為一顆樹，所以左右的方法數相乘)。
所以對於 dp[3] 而言，應該是
左子樹排列種類 x 右子樹排列種類
1 為根節點 dp[0] * dp[2]
2 為根節點 dp[1] * dp[1]
3 為根節點 dp[2] * dp[1]
三種結果相加，最後得到 2 + 1 + 2 = 5。
我們需要預先初始化的 case 為 dp[0] = 1，dp[1] = 1，dp[2] = 2，這都是上面討論過的案例，記得，dp[i] 的涵義就是當有 i 個節點時該樹的排列方式數量。
這邊對比我一開始執著的實際數字，讓我意識到這類問題要嘗試用更抽象的角度去看，如這題我們是專注在 O 個元素的 BST 排列方式，這些元素分別為多少不重要，我們只要知道 BST 在 O 個下的排列方式數量就好，實際排列 BST 會自己完成。

抽象化後，我們可以用上面這個左右子樹相加的概念得出這樣的迴圈式：

for(var i = 3; i <= n; i++){
    for(var j = 1; j <= i; j++){
        dp[i] += dp[j - 1] * dp[i - j];
    }
}

i 代表現在計算 n 個節點遍歷，j 代表計算 n 個節點時分別讓 1 ~ n 做為根節點的可能性，乘法是如上面解釋的，左子樹共有 j - 1 個(比 j 小)元素，右子樹共有 i - j 個(比 j 大)元素。

最後總合起來的程式碼如下：

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

這題初見時應該會覺得挺矇的，但希望走過這題的算法後，有留下一些印象，包含關注排列行為本身、對 BST 的排列意識到根節點決定左右子樹節點個數等等觀點，下次處理類似題目的時候，會更有印象。