96. Unique Binary Search Trees (Medium)

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.

 

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 19

A:
递归调用 方法，

public class UniqueBinarySearchTrees {
    public int numTrees(int n) {
        // DP method
        if (n == 0 || n == 1)
            return 1;
        if (n == 2)
            return 2;
        int sum = 0;
        for (int i = 1; i <= n; i++) { // choose i as the root.
            sum = sum + (numTrees(i - 1) * numTrees(n - i));
        }
        return sum;
    }
}

------------------ From Top Down 。 遇到了就记下来

class Solution {

public:

int numTrees(int n) {

return helper(1,n+1);

}

private:

int helper(int low, int high){

auto it = map.find(high-low);

if( it != map.end()){

return it->second;

}

int sum = 0;

for(int i =low; i<high; i++){

sum += helper(low,i) * helper(i+1,high);

}

map[high-low] = sum;

return sum;

}

unordered_map<int,int> map{{0,1}};

};

--------------------------------------第二遍----  bottom up ,  先算小的---------------------------
           这次是真正的DP       而且是主动DP

class Solution {
public:
    int numTrees(int n) {
        vector<int> A(n + 1, 0);
        A[0] = 1;
        for (int i = 1; i < n + 1; ++i)
            for (int rootVal = 1; rootVal <= i; ++rootVal)
                A[i] += A[rootVal - 1] * A[i - rootVal];
        return A[n];
    }
};

Mistakes:
1： 注意，左右两边，是相乘的关系，（乘法原理）