Evaluate Expression To True

• Time : $O(|s|^3)$
• Space : $O(|s|^2)$

int dp[202][202][2];
int mod = 1e3 + 3;
void helper(string s, int l, int r) {
    if(dp[l][r][0] != -1) return;
    if(l == r) {
        dp[l][r][0] = s[l] == 'F';
        dp[l][r][1] = s[l] == 'T';
    } else {
        int& T = dp[l][r][1] = 0;
        int& F = dp[l][r][0] = 0;
        
        for(int i = l + 1; i < r; i++) {
            if(s[i] == 'T' or s[i] == 'F') continue;
            helper(s,l,i-1);
            helper(s,i+1,r);
            int lt = dp[l][i-1][1];
            int lf = dp[l][i-1][0];
            int rt = dp[i+1][r][1];
            int rf = dp[i+1][r][0];
            if(s[i] == '|') {
                F = (F + lf * rf % mod) % mod;
                T = (T + lf * rt % mod + lt * rf % mod + lt * rt % mod) % mod;
            }
            if(s[i] == '&') {
                F = (F + lf * rf % mod + lf * rt % mod + lt * rf % mod) % mod;
                T = (T + lt * rt % mod) % mod;
            }
            if(s[i] == '^') {
                F = (F + lf * rf % mod + lt * rt % mod) % mod;
                T = (T + lf * rt % mod + lt * rf % mod) % mod;
            }
        }
    }
}
int Solution::cnttrue(string A) {
    memset(dp,-1,sizeof dp);
    helper(A,0,A.size() - 1);
    return dp[0][A.size()-1][1];
}