Leetcode: Unique Binary Search Trees

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

Understand the problem:
The problem gives an integer n, asks for how many structurally unique BSTs that stores value 1 .. n available? 

Solution:
We use DP to solve this problem:
1. Definition: dp[i] means for integer i, how many unique BST's available.
2. Transit Function: dp[i]

For n = 2, dp[2] = dp[0] * dp[1]  // 1 as root 
                          + dp[1] * dp[0] // 2 as root

For n = 3, dp[3] =  dp[0] * dp[2]            // 1 as root
                          +  dp[1] * dp[1]           // 2 as root
                          +  dp[2] * dp[0]           // 3 as root

dp[i] = sum of dp[k] * dp[i - k - 1]; 0 <= k < i

3. Initial state dp[0] = 1; // Mean empty
                      dp[1] = 1; // 1 as root
4. Final state dp[n]

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public 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++) {             for (int j = 0; j < i; j++) {                 dp[i] += dp[j] * dp[i - j - 1];             }         }                   return dp[n];     } }

A Recursive Approach:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Solution {     public int numTrees(int n) {         if (n <= 1) {             return 1;         }                   return numTreesHelper(1, n);     }           private int numTreesHelper(int start, int end) {         if (start >= end) {             return 1;         }                   int totalSum = 0;         for (int i = start; i <= end; i++) {             totalSum += numTreesHelper(start, i - 1) * numTreesHelper(i + 1, end);         }                   return totalSum;     } }

Summary:
The take-away message for DP problem is the four steps approach. 
1. Define a DP array or matrix.
2. Figure out the transit functions.
3. Handle the initial state
4. Figure out the final state