LeetCode-in-All
96. Unique Binary Search Trees
Medium
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
Solution
defmodule Solution do
@spec num_trees(n :: integer) :: integer
def num_trees(n) do
cache = %{0 => 1}
Enum.reduce(1..n, cache, &unique_trees/2)
|> Map.get(n)
end
def unique_trees(n, cache) do
count = Enum.map(1..n, fn r ->
Map.get(cache, r - 1) * Map.get(cache, n - r)
end)
|> Enum.sum()
Map.put(cache, n, count)
end
end