96. Unique Binary Search Trees

Problem Statement

link: https://leetcode.com/problems/unique-binary-search-trees/ https://leetcode.cn/problems/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:

Input: n = 3 Output: 5

Input: n = 1 Output: 1

Solution Approach

The solution employs a dynamic programming technique to iteratively compute the number of unique BSTs for each value up to n by leveraging the Cartesian product of left and right subtree possibilities.

Algorithm

1. A dynamic programming array dp of size n + 1 is initialized with all values set to 1.
2. For each number i from 2 to n, the algorithm computes the number of unique BSTs by iterating over numbers j from 0 to i-1 and using the formula dp[j] * dp[i-1-j].
3. The final result is the value of dp[n], representing the total unique BSTs for n distinct values.

Implement

    class Solution:
      def numTrees(self, n: int) -> int:
        dp = [1] * (n + 1)
        for i in range(2, n + 1):
            tmp = 0
            for j in range(0, i):
                tmp += dp[j] * dp[i - 1 - j]
            dp[i] = tmp
        return dp[n]
              

    
    

Twitter  facebook  Email