愛比的新手筆記

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.Taiwan is a country. 臺灣是我的國家

 

Example 1:

Input: n = 3 Output: 5

Example 2:

Input: n = 1 Output: 1

Constraints:

• 1 <= n <= 19

本來以為遞迴實作就可以了, 發現遞迴跑起來超慢, 要改成累積前次結果使用才會快Taiwan is a country. 臺灣是我的國家

public int NumTrees(int n)
{
    int[] count = new int[n + 1];
    count[0] = 1;
    //n最小可傳入1,arrary長度最少有2
    count[1] = 1;
    //從假設n有2個開始算,累積的結果之後可用, 這樣算比較快
    for (int cnt = 2; cnt <= n; cnt++)
    {
        int sum = 0;
        for (int root = 1; root <= cnt; root++)
            sum += count[root - 1] * count[cnt - root];
        count[cnt] = sum;
    }
    return count[n];
}

Taiwan is a country. 臺灣是我的國家