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

Did this again on 7/4/2016, just to refresh up my mind, still amazed at how the program is come up with, has an array called * dp* to cache the result, also, note the array in the for loop starts from 2, since we have defined dp[0] = dp[1] = 1 already, and they don’t conform to the following formula.

Most highly upvoted posts have this solution, basically, the idea is:

Take n = 5 as an example, we can figure out the number of unique binary search trees as follow, we will use an array *dp[]* of length *n+1 *to hold the cached calculation:

- if we set 1 as root, then there could be
*null*number of BST as its left subtree, and there could be X number of unique BST as its right subtree formed by {2,3,4,5}, and one key point is that the X number of unique BST formed by {2,3,4,5} is exactly the same of that formed by {1,2,3,4}, thus, we could save duplicate calculation and use cached results. (This is Dynamic Programming):- So, the total possibilities of using
*1*as root, is its left subtree possibilities*times*its right subtree possibilities. - we mark this as: dp[0]*dp[4]

- So, the total possibilities of using
- then we continue to set 2 as root, then there could be 1 subtree on its left side, and there could be X number of unique BST on its right formed by {3,4,5}, which is the same number as that formed by {1,2,3}
- we mark this as: dp[1]*dp[3]

- then we continue to set 3 as root, {1,2} will be able to form its left subtree, {4,5} will be able to form its right subtree
- we mark this as: dp[2]*dp[2]

- then, we continue to set 4 as root, {1,2,3} will be able to form its left subtree, {5} will be able to form its right subtree, total possible unique BST using 4 as root will be:
- dp[3]*dp[1]

- finally, we set 5 (n=5 in this example) as root, there will be NO right subtree, {1,2,3,4} will be able to form its left subtree, total possible unique BST using 5 as root will be:
- dp[4][0]

So, we figured out the pattern/algorithm to calculate the total number of possible unique BST given n is:

dp[n] = dp[0]*dp[n-1] //means we set * 1* as root, the possible unique BSTs on its left side times the possible unique BSTs on its right side

+ dp[1]*dp[n-2]//means we set * 2 *as root, the possible unique BSTs on its left side times the possible unique BSTs on its right side

+…

dp[n-1]*dp[0]//means we set * n *as root, the possible unique BSTs on its left side times the possible unique BSTs on its right side

so, it’s like this: * dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + ….+ dp[n-2][1] + dp[n-1][0]*;

Now, it’s time to put it into runnable code, some key notes when converting the above idea into working code:

- remember in the problem statement, it says from 1…n, it rules out 0 as a possible value for treenode, so, in order to correctly calculate the result for n, we need to have an array length of
*n+1*, instead of*n*. - use a nested
*for*loop to implement this (from looking at the pattern of the indices) - we hardcode dp[0] = dp[1] = 1;
- remember that all array elements are initialized to be
*0*, so when we first hit dp[2], it’ll be dp[2] = 0, don’t feel confused that where the initial value of dp[2] will come from

public int numTrees(int n) { int[] dp = new int[n+1]; dp[0] = dp[1] = 1; for(int i = 2; i &lt;= n; i++){ for(int j = 1; j &lt;= i; j++){ dp[i] += dp[i-j]*dp[j-1]; } } return dp[n]; }