Leetcode 96. Unique Binary Search Trees

tags: Leetcode(C++)

題目 : https://leetcode.com/problems/unique-binary-search-trees/ 。

想法 :

​​​​切成左右兩子樹DP，並記憶化搜尋。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int DP(int n, int mem[]){
        if(n == 0) return 1;
        if(mem[n] != 0) return mem[n];
        
        for(int i=1 ; i<=n ; i++){
            mem[n]+=(DP(i-1, mem) * DP(n-i, mem));
        }
        
        return mem[n];
    }
    
    int numTrees(int n) {
        int mem[20]={0};
        
        return DP(n, mem);
    }
};