算法设计（布尔括号问题| DP-37） _动态规划

本文概述

C ++
Java
Python3
C#

给定带有以下符号的布尔表达式。

Symbols 'T' ---> true 'F' ---> false

并在符号之间填充以下运算符

Operators & ---> boolean AND |---> boolean OR ^---> boolean XOR

计算可以在表达式中加上括号的方式的数目, 以便使表达式的值评估为true。
让输入为两个数组的形式, 一个包含顺序的符号(T和F), 另一个包含运算符(＆, |和^}
例子：

Input: symbol[]= {T, F, T} operator[]= {^, & } Output: 2 The given expression is "T ^ F & T", it evaluates true in two ways "((T ^ F) & T)" and "(T ^ (F & T))"Input: symbol[]= {T, F, F} operator[]= {^, |} Output: 2 The given expression is "T ^ F | F", it evaluates true in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )". Input: symbol[]= {T, T, F, T} operator[]= {|, & , ^} Output: 4 The given expression is "T | T & F ^ T", it evaluates true in 4 ways ((T|T)& (F^T)), (T|(T& (F^T))), (((T|T)& F)^T) and (T|((T& F)^T)).

解：
让T(i, j)> 表示在i和j之间(包括两端)加上括号的方式的数量, 以使i和j之间的子表达式求值为true。

文章图片
< ！–

文章图片
–>
让F(i, j)表示在i和j之间(包括两端)加上括号的方式的数量, 以使i和j之间的子表达式求值为false。

文章图片
< ！—

文章图片
–>
基本案例：

T(i, i) = 1 if symbol[i] = 'T' T(i, i) = 0 if symbol[i] = 'F' F(i, i) = 1 if symbol[i] = 'F' F(i, i) = 0 if symbol[i] = 'T'

如果我们绘制上述递归解的递归树, 则可以观察到它有许多重叠的子问题。像其他动态规划问题, 可以通过自下而上的方式填充表格来解决。以下是动态编程解决方案的C++实现。
C ++

#include< iostream> #include< cstring> using namespace std; //Returns count of all possible parenthesizations that lead to //result true for a boolean expression with symbols like true //and false and operators like & , | and ^ filled between symbols int countParenth( char symb[], char oper[], int n) { int F[n][n], T[n][n]; //Fill diaginal entries first //All diagonal entries in T[i][i] are 1 if symbol[i] //is T (true).Similarly, all F[i][i] entries are 1 if //symbol[i] is F (False) for ( int i = 0; i < n; i++) { F[i][i] = (symb[i] == 'F' )? 1: 0; T[i][i] = (symb[i] == 'T' )? 1: 0; }//Now fill T[i][i+1], T[i][i+2], T[i][i+3]... in order //And F[i][i+1], F[i][i+2], F[i][i+3]... in order for ( int gap=1; gap< n; ++gap) { for ( int i=0, j=gap; j< n; ++i, ++j) { T[i][j] = F[i][j] = 0; for ( int g=0; g< gap; g++) { //Find place of parenthesization using current value //of gap int k = i + g; //Store Total[i][k] and Total[k+1][j] int tik = T[i][k] + F[i][k]; int tkj = T[k+1][j] + F[k+1][j]; //Follow the recursive formulas according to the current //operator if (oper[k] == '& ' ) { T[i][j] += T[i][k]*T[k+1][j]; F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]); } if (oper[k] == '|' ) { F[i][j] += F[i][k]*F[k+1][j]; T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]); } if (oper[k] == '^' ) { T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; } } } } return T[0][n-1]; }//Driver program to test above function int main() { char symbols[] = "TTFT" ; char operators[] = "|& ^" ; int n = strlen (symbols); //There are 4 ways //((T|T)& (F^T)), (T|(T& (F^T))), (((T|T)& F)^T) and (T|((T& F)^T)) cout < < countParenth(symbols, operators, n); return 0; }

Java

class GFG {//Returns count of all possible //parenthesizations that lead to //result true for a boolean //expression with symbols like true //and false and operators like & , | //and ^ filled between symbols static int countParenth( char symb[], char oper[], int n) { int F[][] = new int [n][n]; int T[][] = new int [n][n]; //Fill diaginal entries first //All diagonal entries in T[i][i] //are 1 if symbol[i] is T (true). //Similarly, all F[i][i] entries //are 1 if symbol[i] is F (False) for ( int i = 0 ; i < n; i++) { F[i][i] = (symb[i] == 'F' ) ? 1 : 0 ; T[i][i] = (symb[i] == 'T' ) ? 1 : 0 ; }//Now fill T[i][i+1], T[i][i+2], //T[i][i+3]... in order And F[i][i+1], //F[i][i+2], F[i][i+3]... in order for ( int gap = 1 ; gap < n; ++gap) { for ( int i = 0 , j = gap; j < n; ++i, ++j) { T[i][j] = F[i][j] = 0 ; for ( int g = 0 ; g < gap; g++) { //Find place of parenthesization //using current value of gap int k = i + g; //Store Total[i][k] and Total[k+1][j] int tik = T[i][k] + F[i][k]; int tkj = T[k + 1 ][j] + F[k + 1 ][j]; //Follow the recursive formulas //according to the current operator if (oper[k] == '& ' ) { T[i][j] += T[i][k] * T[k + 1 ][j]; F[i][j] += (tik * tkj - T[i][k] * T[k + 1 ][j]); } if (oper[k] == '|' ) { F[i][j] += F[i][k] * F[k + 1 ][j]; T[i][j] += (tik * tkj - F[i][k] * F[k + 1 ][j]); } if (oper[k] == '^' ) { T[i][j] += F[i][k] * T[k + 1 ][j] + T[i][k] * F[k + 1 ][j]; F[i][j] += T[i][k] * T[k + 1 ][j] + F[i][k] * F[k + 1 ][j]; } } } } return T[ 0 ][n - 1 ]; }//Driver code public static void main(String[] args) { char symbols[] = "TTFT" .toCharArray(); char operators[] = "|& ^" .toCharArray(); int n = symbols.length; //There are 4 ways //((T|T)& (F^T)), (T|(T& (F^T))), //(((T|T)& F)^T) and (T|((T& F)^T)) System.out.println(countParenth(symbols, operators, n)); } }//This code has been contributed //by 29AjayKumar

Python3

# Returns count of all possible # parenthesizations that lead to # result true for a boolean # expression with symbols like # true and false and operators # like & , | and ^ filled between symbols def countParenth(symb, oper, n): F = [[ 0 for i in range (n + 1 )] for i in range (n + 1 )] T = [[ 0 for i in range (n + 1 )] for i in range (n + 1 )]# Fill diaginal entries first # All diagonal entries in # T[i][i] are 1 if symbol[i] # is T (true). Similarly, all # F[i][i] entries are 1 if # symbol[i] is F (False) for i in range (n): if symb[i] = = 'F' : F[i][i] = 1 else : F[i][i] = 0if symb[i] = = 'T' : T[i][i] = 1 else : T[i][i] = 0# Now fill T[i][i+1], T[i][i+2], # T[i][i+3]... in order And # F[i][i+1], F[i][i+2], # F[i][i+3]... in order for gap in range ( 1 , n): i = 0 for j in range (gap, n): T[i][j] = F[i][j] = 0 for g in range (gap):# Find place of parenthesization # using current value of gap k = i + g# Store Total[i][k] and Total[k+1][j] tik = T[i][k] + F[i][k]; tkj = T[k + 1 ][j] + F[k + 1 ][j]; # Follow the recursive formulas # according to the current operator if oper[k] = = '& ' : T[i][j] + = T[i][k] * T[k + 1 ][j] F[i][j] + = (tik * tkj - T[i][k] * T[k + 1 ][j]) if oper[k] = = '|' : F[i][j] + = F[i][k] * F[k + 1 ][j] T[i][j] + = (tik * tkj - F[i][k] * F[k + 1 ][j]) if oper[k] = = '^' : T[i][j] + = (F[i][k] * T[k + 1 ][j] + T[i][k] * F[k + 1 ][j]) F[i][j] + = (T[i][k] * T[k + 1 ][j] + F[i][k] * F[k + 1 ][j]) i + = 1 return T[ 0 ][n - 1 ] # Driver Code symbols = "TTFT" operators = "|& ^" n = len (symbols)# There are 4 ways # ((T|T)& (F^T)), (T|(T& (F^T))), # (((T|T)& F)^T) and (T|((T& F)^T)) print (countParenth(symbols, operators, n))# This code is contributed by # sahil shelangia

//C# program of above approach using System; class GFG {//Returns count of all possible //parenthesizations that lead to //result true for a boolean //expression with symbols like true //and false and operators like & , | //and ^ filled between symbols static int countParenth( char []symb, char []oper, int n) { int [, ]F = new int [n, n]; int [, ]T = new int [n, n]; //Fill diaginal entries first //All diagonal entries in T[i, i] //are 1 if symbol[i] is T (true). //Similarly, all F[i, i] entries //are 1 if symbol[i] is F (False) for ( int i = 0; i < n; i++) { F[i, i] = (symb[i] == 'F' ) ? 1 : 0; T[i, i] = (symb[i] == 'T' ) ? 1 : 0; }//Now fill T[i, i+1], T[i, i+2], //T[i, i+3]... in order And F[i, i+1], //F[i, i+2], F[i, i+3]... in order for ( int gap = 1; gap < n; ++gap) { for ( int i = 0, j = gap; j < n; ++i, ++j) { T[i, j] = F[i, j] = 0; for ( int g = 0; g < gap; g++) { //Find place of parenthesization //using current value of gap int k = i + g; //Store Total[i, k] and Total[k+1, j] int tik = T[i, k] + F[i, k]; int tkj = T[k + 1, j] + F[k + 1, j]; //Follow the recursive formulas //according to the current operator if (oper[k] == '& ' ) { T[i, j] += T[i, k] * T[k + 1, j]; F[i, j] += (tik * tkj - T[i, k] * T[k + 1, j]); } if (oper[k] == '|' ) { F[i, j] += F[i, k] * F[k + 1, j]; T[i, j] += (tik * tkj - F[i, k] * F[k + 1, j]); } if (oper[k] == '^' ) { T[i, j] += F[i, k] * T[k + 1, j] + T[i, k] * F[k + 1, j]; F[i, j] += T[i, k] * T[k + 1, j] + F[i, k] * F[k + 1, j]; } } } } return T[0, n - 1]; }//Driver code public static void Main() { char []symbols = "TTFT" .ToCharArray(); char []operators = "|& ^" .ToCharArray(); int n = symbols.Length; //There are 4 ways //((T|T)& (F^T)), (T|(T& (F^T))), //(((T|T)& F)^T) and (T|((T& F)^T)) Console.WriteLine(countParenth(symbols, operators, n)); } }/* This code contributed by PrinciRaj1992 */

输出如下：

4

【算法设计（布尔括号问题| DP-37）】时间复杂度：O(n^3)
辅助空间：O(n^2)
参考文献：
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_9.swf
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。