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

## No comments:

## Post a Comment