DP 52: Evaluate Boolean Expression to True | Partition DP

This chapter covers the classic "Evaluate Boolean Expression to True" problem using Partition Dynamic Programming (MCM-style). Building directly upon concepts established in Matrix Chain Multiplication (DP 48-51), this lesson teaches how to partition a boolean expression at every operator, evaluate left and right subproblems independently for both true and false outcomes, and combine their ways using combinatorial rules for logical operators (AND, OR, XOR).

1. Why Do We Need This? (Problem Statement & Status Quo)

Given a boolean expression string consisting of operands (T for true, F for false) and operators (& for AND, | for OR, ^ for XOR), we need to find the total number of ways to parenthesize or evaluate the expression such that the final resulting value evaluates to True.

Example Walkthrough

• Expression: T | T & F
• Naive Approach 1: Solve (T | T) & F $\rightarrow$ T & F $\rightarrow$ F (Evaluates to False)
• Naive Approach 2: Solve T | (T & F) $\rightarrow$ T | F $\rightarrow$ T (Evaluates to True)
• Total Ways to True: 1 way.

As expressions grow longer, brute-force evaluation leads to overlapping subproblems and exponential time complexity. We need a systematic way to partition the expression at every operator, solve sub-expressions, and combine their counts.

2. Core Mental Model: The Matrix Chain Multiplication (MCM) Parallel

Just like splitting a chain of matrices at every possible multiplication index k:

Matrix Chain:    [A] [B] [C] [D]
Boolean String:   T   |   T   &   F   ^   T
                  i       k       j

In Partition DP for boolean expressions:

• The expression string ranges from index i to j.
• Operands (T or F) are at even indices (0, 2, 4, ...).
• Operators (&, |, ^) are at odd indices (1, 3, 5, ...).
• We make our partitions exclusively at operators (at a distance of 2 indices: i + 1, i + 3, ..., j - 1).

3. Naive vs. Better Approach: Why We Need Both True & False Counts

When we partition an expression at an operator index into a Left Subproblem (i to index - 1) and a Right Subproblem (index + 1 to j), what does each subproblem need to return?

If we evaluate an OR expression, a True result can come from various combinations:

1. True on Left AND True on Right (T | T = T)
2. True on Left AND False on Right (T | F = T)
3. False on Left AND True on Right (F | T = T)

Therefore, simply counting the ways a subproblem evaluates to True is insufficient. Every subproblem must return both:

1. The number of ways it evaluates to True.
2. The number of ways it evaluates to False.

4. Combinatorial Rules for Operators (AND, OR, XOR)

Let:

• lt: Number of ways left subproblem evaluates to True
• lf: Number of ways left subproblem evaluates to False
• rt: Number of ways right subproblem evaluates to True
• rf: Number of ways right subproblem evaluates to False

Depending on the operator at index, the ways to accumulate True (isTrue = 1) and False (isTrue = 0) are defined as follows:

5. Step-by-Step Recursive Function Design

Parameters

• i: Starting index of the expression range.
• j: Ending index of the expression range.
• isTrue: Flag (1 if we want the number of ways to evaluate to True, 0 for False).

Base Cases

1. Invalid Range (i > j):
   C++

   Copy

   if (i > j) return 0;
   

2. Single Element Range (i == j):
   C++

   Copy

   if (i == j) {
       if (isTrue == 1) return exp[i] == 'T' ? 1 : 0;
       else return exp[i] == 'F' ? 1 : 0;
   }
   

Partition Loop

We iterate index from i + 1 to j - 1, stepping by 2 (since operators are at odd positions):

long long ways = 0;
long long MOD = 1000000007;

for (int index = i + 1; index <= j - 1; index += 2) {
    long long lt = f(i, index - 1, 1, exp);
    long long lf = f(i, index - 1, 0, exp);
    long long rt = f(index + 1, j, 1, exp);
    long long rf = f(index + 1, j, 0, exp);
    
    char op = exp[index];
    
    if (op == '&') {
        if (isTrue) ways = (ways + lt * rt) % MOD;
        else ways = (ways + lf * rf + lf * rt + lt * rf) % MOD;
    }
    else if (op == '|') {
        if (isTrue) ways = (ways + lt * rt + lt * rf + lf * rt) % MOD;
        else ways = (ways + lf * rf) % MOD;
    }
    else if (op == '^') {
        if (isTrue) ways = (ways + lt * rf + lf * rt) % MOD;
        else ways = (ways + lt * rt + lf * rf) % MOD;
    }
}
return ways;

6. Complete Memoized Solution (C++)

To avoid exponential time complexity caused by overlapping subproblems, we use a 3D DP table of size [N][N][2], where:

• First dimension N: Start index i (0 to N-1)
• Second dimension N: End index j (0 to N-1)
• Third dimension 2: Boolean flag isTrue (0 or 1)

#include <bits/stdc++.h>
using namespace std;

long long MOD = 1000000007;

long long solveMemo(int i, int j, int isTrue, string &exp, vector<vector<vector<long long>>> &dp) {
    // Base Case 1: Invalid range
    if (i > j) return 0;
    
    // Base Case 2: Single character
    if (i == j) {
        if (isTrue == 1) return exp[i] == 'T' ? 1 : 0;
        else return exp[i] == 'F' ? 1 : 0;
    }
    
    // Check Memo Table
    if (dp[i][j][isTrue] != -1) return dp[i][j][isTrue];
    
    long long ways = 0;
    
    for (int index = i + 1; index <= j - 1; index += 2) {
        long long lt = solveMemo(i, index - 1, 1, exp, dp);
        long long lf = solveMemo(i, index - 1, 0, exp, dp);
        long long rt = solveMemo(index + 1, j, 1, exp, dp);
        long long rf = solveMemo(index + 1, j, 0, exp, dp);
        
        char op = exp[index];
        
        if (op == '&') {
            if (isTrue) ways = (ways + (lt * rt) % MOD) % MOD;
            else ways = (ways + (lf * rf) % MOD + (lf * rt) % MOD + (lt * rf) % MOD) % MOD;
        }
        else if (op == '|') {
            if (isTrue) ways = (ways + (lt * rt) % MOD + (lt * rf) % MOD + (lf * rt) % MOD) % MOD;
            else ways = (ways + (lf * rf) % MOD) % MOD;
        }
        else if (op == '^') {
            if (isTrue) ways = (ways + (lt * rf) % MOD + (lf * rt) % MOD) % MOD;
            else ways = (ways + (lt * rt) % MOD + (lf * rf) % MOD) % MOD;
        }
    }
    
    return dp[i][j][isTrue] = ways;
}

int evaluateTrue(string exp) {
    int n = exp.size();
    // 3D DP table initialized to -1: dimensions [n][n][2]
    vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(n, vector<long long>(2, -1)));
    return solveMemo(0, n - 1, 1, exp, dp);
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Partition DP Application: This problem extends Matrix Chain Multiplication principles by partitioning strings at operator boundaries rather than matrix multiplication indices.
• Dual Tracking: Because logical operations depend on combinations of both true and false evaluations, subproblems must calculate and return both true and false counts (lt, lf, rt, rf).
• Operator Combinatorics: Break down boolean logic into distinct modular equations for AND, OR, and XOR depending on whether the target is isTrue = 1 or isTrue = 0.
• Modulo Arithmetic: Because the number of evaluation ways grows exponentially, always apply modulo 10^9 + 7 at every addition step to prevent integer overflow.
• 3D Memoization: States are defined uniquely by (i, j, isTrue), requiring an N × N × 2 lookup table to optimize exponential recursion down to $O(N^3)$ time.