20 Nov 2016

# Recursion to 1 dimensional dynamic programing II

Author: derek0883@gmail.com

This article will show you how to use recursion method solve problem, then easily lead to a 1 dimensional dynamic programing solution.

## Unique Binary Search Trees

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
``````

### DFS solution

With input is n, 1st step, we have n options, e.g. For is 3, we have 3 options: use 1,2 or 3 as root node. with each option, we got two new sub problem. How many way to form left sub-tree and right sub-tree. Once we solved left sub problem and right sub problem, the number of ways is production of L and R.

Termination condition is, n is 0, empty tree, or n is 1, only one node.

This is very good problem to understanding recursion, unlike previous problems, each step, we have N options, and for each option, we got two new sub-problems.

``````public int numTrees(int n) {
return dfs(0, n-1);
// return dfsCache(0, n-1);
// return dp(n);
}
private int dfs(int L, int R) {
if (L >= R) return 1;
int nWay = 0;
for (int i = L; i <= R; i++) {
nWay += dfs(L, i-1) * dfs(i+1, R);
}
return nWay;
}
``````

### DFS + memorize O(n) time complexity solution

``````private int dfsCache(int L, int R) {
int[] cache = new int[R-L+1];
return dfsCache(L, R, cache);
}
private int dfsCache(int L, int R, int[] cache) {
if (L >= R) return 1;
if (cache[R-L] != 0)
return cache[R-L];
int nWay = 0;
for (int i = L; i <= R; i++) {
nWay += dfsCache(L, i-1, cache) * dfsCache(i+1, R, cache);
}
cache[R-L] = nWay;
return nWay;
}
``````

### DP O(n) time complexity solution

Again, Just convert termination status of DFS cache version into initialize status of DP version, options are same.

``````private int dp(int n) {
int[] fn = new int[n+1];
fn = 1; // empty tree
fn = 1; // 1 node tree
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++)
fn[i] += fn[j] * fn[i-j-1];
}
return fn[n];
}
``````