## Algorithm

Problem Nmae: 96. Unique Binary Search Trees

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

Example 1:

```Input: n = 3
Output: 5
```

Example 2:

```Input: n = 1
Output: 1
```

Constraints:

• `1 <= n <= 19`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int numTrees(int n) {
int *dp;
int i, j;

dp = calloc((n + 1), sizeof(int));
//assert(dp);

dp[0] = dp[1] = 1;

for (i = 2; i <= n; i ++) {
for (j = 1; j <= i; j ++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}

i = dp[n];
free(dp);

return i;
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
5

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
5

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numTrees = function(n) {
const arr = new Array(n + 1).fill(0)
arr[0] = arr[1] = 1
for (let i = 2; i <= n; i++) {
for (let j = 1; j <= i; j++) {
arr[i] += arr[j - 1] * arr[i - j]
}
}
return arr[n]
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
1

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numTrees(self, n):
if n <= 1:
return 1
catalan = [0] * (n + 1)
catalan[0] = catalan[1] = 1
for i in range(2, n + 1):
for j in range(i):
catalan[i] += catalan[j] * catalan[i - j - 1]
return catalan[n]
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
1

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _096_UniqueBinarySearchTree
{
public int NumTrees(int n)
{
long result = 1;
for (int i = 0; i < n; i++)
result = result * 2 * (2 * i + 1) / (i + 2);

return (int)result;
}
}
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
5