Dynamic Programming • Interval DP

Boolean Parenthesization

Find the number of ways to parenthesize a boolean expression so that it evaluates to True.

Overview

This is a classic Interval DP problem. We evaluate every possible substring and partition it into left and right sub-expressions.

Two States

Because operators like XOR (`^`) need both True and False values to produce True, we must track the number of ways to evaluate to both True and False.

Partitioning

For a substring from `i` to `j`, we iterate a split point `k` on the operators. The total combinations come from multiplying the left ways and right ways.

Key Insight

By splitting at the operator, we reduce the problem to two smaller, independent problems. The results are combined based on the truth table of the operator.

T

|

T

&

F

^

T

Code Tracker

:::

1for (let len = 3; len <= N; len += 2)

2 for (let i = 0; i <= N - len; i += 2) {

3 let j = i + len - 1;

4 for (let k = i + 1; k < j; k += 2) {

5 let leftT = dpT[i][k-1], leftF = dpF[i][k-1];

6 let rightT = dpT[k+1][j], rightF = dpF[k+1][j];

7 // update dpT[i][j] and dpF[i][j] based on op S[k]

8 }

9 }