一、原題

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
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

二、題意

給定數(shù)字n，求問由1～n的數(shù)字所構(gòu)成的不同二叉搜索樹（BST）的數(shù)目。

三、思路

先從簡單的分析起：

• n = 1：很容易想到結(jié)果為1；
• n = 2：很容易想到結(jié)果是2；
• n = 3：此時(shí)可以考慮成：
• 將數(shù)字3插入到數(shù)字2的所有BST中，則此時(shí)數(shù)字3在2的所有BST中的位置都是固定的，也就是將數(shù)字3插入到數(shù)字2的所有BST后，新生成的樹個(gè)數(shù)等于原來數(shù)字2的BST的數(shù)目，等于2；
• 將數(shù)字3插入到數(shù)字1的所有BST中，同理位置也是固定的（1的右子樹），但此時(shí)有個(gè)問題就是2尚未插入到新的二叉樹中，則2插入的位置也是固定的，那最終生成的二叉樹個(gè)數(shù)，等于1；
• 最后是3作為根：則考慮將1、2插入到3作為根的BST中，因?yàn)?最大，所以1、2插入的位置肯定在3的左子樹，就相當(dāng)于數(shù)字2的所有BST作為3的左子樹，所以數(shù)目等于數(shù)字2的BST的數(shù)目，等于2；
• 綜上：數(shù)字3的BST數(shù)目為2 + 1 + 2 = 5；
• 尚未能明顯總結(jié)出規(guī)律，繼續(xù)推斷，n = 4：
• 將數(shù)字4插入到數(shù)字3的BST中，4的插入位置唯一，生成的數(shù)量等于3的BST數(shù)目，等于5；
• 將數(shù)字4插入到數(shù)字2的BST中，則4作為右子樹，然后再插入數(shù)字3，3插入的位置是固定的，又因?yàn)?的BST數(shù)量為2，所以4的位置有兩種，因此該情況生成的BST數(shù)目等于2；
• 將數(shù)字4插入到數(shù)字1的BST中，則4同樣作為右子樹，此時(shí)需要插入數(shù)字3和2，此時(shí)3和2構(gòu)成的BST肯定作為4的最字?jǐn)?shù)，所以數(shù)量上等于2的BST，等于2；
• 將數(shù)字4作為根，所以新生成的BST數(shù)量等于數(shù)字3的BST數(shù)量；
• 綜上：數(shù)字4的BST數(shù)目為5 +２ + 2 + 5 = 14

....

綜上，假設(shè)要求數(shù)目為n的BST數(shù)目，dp[i]用來表示數(shù)量為i的BST數(shù)目：

• n作為根：生成BST數(shù)量為等于(n-1)的BST數(shù)目：dp[n - 1]；
• n插入到(n-1)的BST中：數(shù)量為dp[n - 1]；
• n插入到(n-2)的BST中，則尚未插入的數(shù)據(jù)還有數(shù)字(n-1)，則最終生成的數(shù)量為dp[n - 2]
• n插入到(n-3)的BST中，則尚未插入的數(shù)據(jù)還有數(shù)字(n-2)和(n-1)，則最終生成的數(shù)量為dp[n - 3] * dp[2]
  ....
• n插入到(n-i)的BST中，則尚未插入的數(shù)據(jù)還有數(shù)字(n - 1)、(n - 2)、...、(n - i + 1)，因?yàn)閚插入到(n-i)的BST中，則n都是作為右子樹且插入位置唯一，所以新生成的數(shù)量等于(n - 1)、(n - 2)、...、(n - i + 1)這幾個(gè)數(shù)字構(gòu)成的BST的數(shù)目，所以生成的數(shù)目為：dp[n - i] * dp[i - 1]；

故 $$dp[n] = \sum\limits_{i = 1}^{n - 1} (dp[n - i] * dp[i - 1])$$

四、代碼

class Solution {
public:
    int numTrees(int n) {
        if(n <= 1){
            return 1;
        }

        int *dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

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

        int res = dp[n];
        delete[] dp;
        return res;
    }
};