Boolean Parenthesization — Solution & Editorial

Back to the Problem

Interval DP tracking, for each subexpression, the counts of parenthesizations giving True and False; combine children according to the operator.

Complexity: O(n³)

Watch out: Track both True and False counts; the False count for & is total−TrueTrue, etc.