Dynamic Programming:
Placing Parentheses
Alexander S. Kulikov
Steklov Institute of Mathematics at St. Petersburg
Russian Academy of Sciences
Algorithmic Design and Techniques
Algorithms and Data Structures
Outline
1 Problem Overview
2 Subproblems
3 Algorithm
4 Reconstructing a Solution
How to place parentheses in an expression
1+2−3×4−5
to maximize its value?
How to place parentheses in an expression
1+2−3×4−5
to maximize its value?
Example
((((1 + 2) − 3) × 4) − 5) = −5
How to place parentheses in an expression
1+2−3×4−5
to maximize its value?
Example
((((1 + 2) − 3) × 4) − 5) = −5
((1 + 2) − ((3 × 4) − 5)) = −4
Answer
((1 + 2) − (3 × (4 − 5))) = 6
Another example
What about
5 − 8 + 7 × 4 − 8 + 9?
Another example
What about
5 − 8 + 7 × 4 − 8 + 9?
Soon
We’ll design an efficient dynamic
programming algorithm to find the answer.
Outline
1 Problem Overview
2 Subproblems
3 Algorithm
4 Reconstructing a Solution
Placing parentheses
Input: A sequence of digits d1, . . . , dn and
a sequence of operations
op1, . . . , opn−1 ∈ {+, −, ×}.
Output: An order of applying these
operations that maximizes the
value of the expression
d1 op1 d2 op2 · · · opn−1 dn .
Intuition
Assume that the last operation in an
optimal parenthesizing of
5 − 8 + 7 × 4 − 8 + 9 is ×:
(5 − 8 + 7) × (4 − 8 + 9) .
Intuition
Assume that the last operation in an
optimal parenthesizing of
5 − 8 + 7 × 4 − 8 + 9 is ×:
(5 − 8 + 7) × (4 − 8 + 9) .
It would help to know optimal values for
subexpressions 5 − 8 + 7 and 4 − 8 + 9.
However
We need to keep track for both the minimal
and the maximal values of subexpressions!
Example: (5 − 8 + 7) × (4 − 8 + 9)
min(5 − 8 + 7) = (5 − (8 + 7)) = −10
max(5 − 8 + 7) = ((5 − 8) + 7) = 4
min(4 − 8 + 9) = (4 − (8 + 9)) = −13
max(4 − 8 + 9) = ((4 − 8) + 9) = 5
Example: (5 − 8 + 7) × (4 − 8 + 9)
min(5 − 8 + 7) = (5 − (8 + 7)) = −10
max(5 − 8 + 7) = ((5 − 8) + 7) = 4
min(4 − 8 + 9) = (4 − (8 + 9)) = −13
max(4 − 8 + 9) = ((4 − 8) + 9) = 5
max((5 − 8 + 7) × (4 − 8 + 9)) = 130
Subproblems
Let Ei,j be the subexpression
di opi · · · opj−1 dj
Subproblems
Let Ei,j be the subexpression
di opi · · · opj−1 dj
Subproblems:
M(i, j) = maximum value of Ei,j
m(i, j) = minimum value of Ei,j
Recurrence Relation
⎧
⎪
⎪M(i, k) opk M(k + 1, j)
⎪
⎨M(i, k) opk m(k + 1, j)
M(i, j) = max
i≤k≤j−1 ⎪
⎪m(i, k) opk M(k + 1, j)
⎪
m(i, k) opk m(k + 1, j)
⎩
⎧
⎪
⎪M(i, k) opk M(k + 1, j)
⎪
⎨M(i, k) opk m(k + 1, j)
m(i, j) = min
i≤k≤j−1 ⎪
⎪m(i, k) opk M(k + 1, j)
⎪
m(i, k) opk m(k + 1, j)
⎩
Outline
1 Problem Overview
2 Subproblems
3 Algorithm
4 Reconstructing a Solution
MinAndMax(i, j)
min ← +∞
max ← −∞
for k from i to j − 1:
a ← M(i, k) opk M(k + 1, j)
b ← M(i, k) opk m(k + 1, j)
c ← m(i, k) opk M(k + 1, j)
d ← m(i, k) opk m(k + 1, j)
min ← min(min, a, b, c, d )
max ← max(max, a, b, c, d )
return (min, max)
Order of Subproblems
When computing M(i, j), the values of
M(i, k) and M(k + 1, j) should be
already computed.
Solve all subproblems in order of
increasing (j − i).
Possible Order
1 n
1
n
Parentheses(d1 op1 d2 op2 . . . dn )
for i from 1 to n:
m(i, i) ← di , M(i, i) ← di
for s from 1 to n − 1:
for i from 1 to n − s:
j ←i +s
m(i, j), M(i, j) ← MinAndMax(i, j)
return M(1, n)
Example: 5 − 8 + 7 × 4 − 8 + 9
5 -3 -10 -55 -63 -94 5 -3 4 25 65 200
8 15 36 -60 -195 8 15 60 52 75
7 28 -28 -91 7 28 20 35
4 -4 -13 4 -4 5
8 17 8 17
9 9
m M
Outline
1 Problem Overview
2 Subproblems
3 Algorithm
4 Reconstructing a Solution
Example: 5 − 8 + 7 × 4 − 8 + 9
5 -3 -10 -55 -63 -94 5 -3 4 25 65 200
8 15 36 -60 -195 8 15 60 52 75
7 28 -28 -91 7 28 20 35
4 -4 -13 4 -4 5
8 17 8 17
9 9
m M
