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):

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:

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