Булевая скобка в C++

Question

Задача булевской задачи состоит в том, чтобы подсчитать количество способов вставить в скобки заданное двоичное выражение так, чтобы оно оценивалось как true.

Я написал решение C++ в соответствии с приведенным объяснением here (small video explanation here), но он всегда возвращает ноль. Мой код кажется очень похожим на код, указанный на первой странице (я не смотрел, прежде чем писать), но он работает там, где у меня нет. Какую ошибку я делаю?

#include <iostream> 
#include <vector> 
#include <map> 
#include <queue> 
#include <algorithm> 

using namespace std; 

int main() { 
    int n; 
    cin >> n; 

    vector<int> vals(n); 
    vector<int> ops(n - 1); //ops[n] is the operator 
          //between the nth and (n-1)th values 
    char tmp; 

    for(int i = 0; i < 2 * n - 1; ++i) { 
     if(i % 2 == 0) { 
      cin >> vals[i/2]; 
     } else { 
      cin >> ops[i/2]; 
     } 
    } 

    vector<vector<int> > t(n, vector<int>(n, 0)), 
         f(n, vector<int>(n, 0)); 

    for(int i = 0; i < n; ++i) { 
     t[i][i] = vals[i] == 1; 
     f[i][i] = vals[i] == 0; 
    } 

    const int AND = 6, OR = 1, XOR = 4; 

    for(int i = 0; i < n - 2; ++i) { 
     for(int j = i + 1; j < n - 1; ++j) { 
      for(int k = i; k < j; ++k) { 
       cout << endl << i << " " << j << " " << k << endl; 
       switch(ops[k]) { 
        case AND: 
         t[i][j] = t[i][k] * t[k + 1][j]; //T & T = T 
         f[i][j] = f[i][k] * f[k + 1][j] //F & F = F 
           + f[i][k] * t[k + 1][j] //F & T = F 
           + t[i][k] * f[k + 1][j]; //T & F = F 

        case OR: 
         t[i][j] = t[i][k] * t[k + 1][j] //etc 
           + f[i][k] * t[k + 1][j] 
           + t[i][k] * f[k + 1][j]; 
         f[i][j] = f[i][k] * f[k + 1][j]; 

        case XOR: 
         t[i][j] = f[i][k] * t[k + 1][j] 
           + t[i][k] * f[k + 1][j]; 
         f[i][j] = f[i][k] * f[k + 1][j] 
           + t[i][k] * t[k + 1][j]; 
       } 

       for(int i = 0; i < n; ++i) { 
        for(int j = 0; j < n; ++j) { 
         cout << t[i][j] << " "; 
        } 
        cout << endl; 
       } 
      } //k loop 
     } //j loop 
    } //i loop 

    cout << endl << t[0][n - 1]; 
} 

Answer 1

Внешние две петли (i и j) не являются правильными. То, что вы делаете в своем коде, начинается с одного конца выражения, перемещаясь к другому концу (цикл i) и пытайтесь рассчитать все более широкие подвыражения, которые начинаются с текущей позиции (ширина j - i, цикл j). Проблема в том, что для вычисления вариаций в скобках для выражения ширины k вам нужны все значения для его подвыражений ширины k - 1 и меньше, что в вашем решении вы еще не рассчитали (не все из них, так или иначе). Итак, вы полагаетесь на значения, которые еще не рассчитаны, а по умолчанию - 0, что дает вам хорошие жирные нули в этих умножениях.

Как и с любой динамической задачи программирования, хитрость заключается в том, чтобы собрать все значения ширины kтолько после того, как вы рассчитали все соответствующие значения для ширины k - 1. Таким образом, внешние две петли должны выглядеть примерно так:

//You've calculated width 0 in the loop before, so start at 1. 
for(int width = 1; width < n; ++width) 
    for(int i = 0, j = i + width; j < n; ++i, ++j) 
     //The inner loop looks OK at first glance, 
     //but I haven't looked at it in depth. 

Имейте в виду, это тестировался, невыполненными код, это только на основе моего понимания динамической задачи программирования в этом случае (мое понимание было время от времени неизвестно). Тем не менее, это должно дать вам начало в расчистке вещей.