# Unique Binary Search Trees - Catalan Numbers

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.

```
public int numTrees(int n) {
int [] dp = new int[n+1];
dp[0]= 1;
dp[1] = 1;
for(int level = 2; level <=n; level++)
for(int root = 1; root<=level; root++)
dp[level] += dp[level-root]*dp[root-1];
return dp[n];
}
```

## Related Problems

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.

Given two strings s and t, return *the number of distinct* **subsequences*** of *s* which equals *t.

Given strings s1, s2, and s3, find whether s3 is formed by an **interleaving** of s1 and s2.