Parentheses

Given a sequence $a_{1}, a_{2}, \dots, a_{n}$ of $n$ numbers separated by $n - 1$ binary operators
Goal: Count all possible valid ways to parenthesize the sequence, foucsing on the order of operations but not the actual values of the numbers
Example:
- $P (1) = 1$
  - $(a_{1})$
- $P (2) = 1$
  - $(a_{1} a_{2})$
- $P (3) = 2$
  - $(a_{1} (a_{2} a_{3}))$
  - $((a_{1} a_{2}) a_{3})$
- $P (4) = 5$
  - $(a_{1} (a_{2} (a_{3} a_{4})))$
  - $(a_{1} ((a_{2} a_{3}) a_{4}))$
  - $((a_{1} a_{2}) (a_{3} a_{4}))$
  - $((a_{1} (a_{2} a_{3})) a_{4})$
  - $(((a_{1} a_{2}) a_{3}) a_{4})$
Recursive Formula:
- $P (n) = i = 1 \sum n - 1 P (i) P (n - i)$
  - Where $i$ splits the sequence into a left part with $i$ elements and a right part with $n - i$ elements
- Base cases: $P (1) = P (2) = 1$
Dynamic Programming Optimization:
- Use an array dp to store results for subproblems
- Initialize dp[1]=dp[2]=1

def count_parentheses(n):
    # Base cases
    if n <= 2:
        return 1
    
    # Initialize a table to store results for subproblems
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 1
    
    # Fill the table iteratively
    for m in range(3, n + 1):
        for i in range(1, m):  # Split into two parts
            dp[m] += dp[i] * dp[m - i]
    
    return dp[n]

Explorer

Parentheses

Backlinks