0:49

Well, in particular, we see by reading the contents of this cell

Â capital M of (1,6) that the maximal value of our initial expression is equal to 200,

Â and our goal is to unwind the whole solution, I mean,

Â parenthesizing of the initial expression, from these two tables.

Â So our first goal on this way is to understand from which two

Â subexpressions of the initial expression the value 200 was computed.

Â 1:22

Well, let's see, when computing the value for the maximal value for

Â subexpression (1,6), we tried all possible splittings

Â of the expression (1,6) into two subexpressions.

Â Well, let's just go through all of them.

Â The first possibility is to split it into two subexpressions (1,1),

Â which corresponds just to the first digit which

Â is just 5, and subexpression (2,6),

Â with a minus sign between them, right.

Â So for both these two subexpressions we already know minimal values and

Â maximal values.

Â Well, let me mark them.

Â So this is the minimal value for the subexpression (1,1).

Â This is the maximal value for subexpression (1,1).

Â For (2,6), this is the minimal value,

Â -195, and this is a maximal value, 75.

Â So we would like to maximize this subexpression

Â one minus subexpression two, which means that we would like the first subexpression

Â to be as large as possible and the second subexpression to be as small as possible.

Â Well, this means that we need to

Â try to take the maximal value of the first subexpression which is five and

Â the minimal value of the second subexpression which is -195.

Â Well, we see that in this case,

Â 5 minus -195 is the same as 5 plus 195,

Â which equals exactly 200, right,

Â which allows us to conclude, actually,

Â that the value 200 can be obtained as follows.

Â So, we subtract the minimum value which is -195

Â over the second subexpression from 5, right.

Â So we restored the last operation in an optimal

Â parenthesizing of the initial expression.

Â However, we still need to find out how to obtain

Â -195 out of the second subexpression.

Â Well, let's do this.

Â 4:02

Well, there are several possible splittings, once again,

Â of the subexpression (2,6) into two smaller sub-subexpressions.

Â The first of them is to split (2,6) into (2,2),

Â which just corresponds to the digit 8 plus (3,6).

Â Well, in this case, we would like the value to be as small as possible and

Â our sign is plus in this case, which means that we would like the value of

Â subexpression (2,2) to be as small as possible and

Â the value of subexpression (3,6) also to be as small as possible.

Â And you already know these values, they are in our tables,

Â so the minimal value of subexpression (2,2) is 8,

Â while the minimum value of subexpression (3, 6) is minus 91, right.

Â So we see that the sum of these two values is not equal to -195,

Â right, which means that plus is not the last operation

Â in the optimal parenthesizing that gives the minimum

Â value of subexpression (2, 6), right.

Â So let's check the next one.

Â Another possibility to split the subexpression (2, 6) is the following.

Â We split it into subexpression (2,

Â 3) times subexpression (4, 6), right.

Â So once again, we would like to find the minimum value of subexpression (2, 6).

Â Well, let's see just all possibilities.

Â The minimum value of subexpression (2, 3) is 15.

Â 6:04

And we would like the product of these two values to be as small as possible.

Â Well, it is not difficult to see that if we take just 15 and

Â multiply it, which is a minimum value of subexpression (2,3),

Â and multiply it by the minimum value of the subexpression (4,6),

Â which is -13, then we get exactly -195.

Â And this, in turn, allows us to get -195

Â from the subexpression (2,6).

Â We can do as follows.

Â We can first compute the sum of 8 and 7.

Â This gives us 15.

Â And then to multiply it by the result of the second subexpression.

Â 6:50

Well, now it remains to find out how to get -13 out of this subexpression for

Â 6, but in this small example, it is already easy to get -13.

Â Well, we just first compute the sum of 8 and 9 and

Â then subtract it from 4, right.

Â So this way we reconstructed the whole solution, I mean,

Â an optimal parenthesizing, or an optimal ordering, of our arithmetic operations,

Â leading to this value, to this maximal value, 200.

Â Let's just check it once again that our parenthesizing leads to the value 200,

Â indeed.

Â So we first compute the sum of 8 and 9.

Â This gives us 17.

Â We then subtract 17 from 4.

Â And this gives us -13.

Â We then compute the sum of 8 and 7.

Â This gives us 15.

Â We multiply 15 by -13.

Â It gives us -195, and, finally,

Â we subtract this number from 5, and we get 200, indeed.

Â So we reconstructed the whole solution.

Â In general, I mean for an expression consisting of n digits and

Â n minus 1 operations they can respond, an algorithm makes roughly quadratic number

Â of steps, because it needs to reconstruct n minus one operations, I mean,

Â an order of n minus one operations, going from last one to the first one.

Â And for each operation, it potentially needs to go through all possible

Â splittings into two subexpressions, and this number is at most M.

Â So the running time is bigger of ten times M, which is bigger of M squared.

Â And this technique is quite general.

Â It applies in many cases in the dynamic problem in algorithms.

Â