0:00

Hello, and welcome to the next lesson in the dynamic programming module.

Â In this lesson, we will be applying the dynamic programming technique for solving

Â a wide range of problems where your goal is to find an optimal order of something.

Â We will illustrate this technique by solving

Â the so-called placing parentheses problem.

Â In this problem, your input is an arithmetic expression consisting of

Â numbers or digits and arithmetic operations, and your goal is to find

Â an order of applying these arithmetic operations that maximizes the radian.

Â You specify this order by placing parentheses, and

Â that's why the problem is called placing parentheses.

Â 0:47

Consider the following toy arithmetic expression.

Â 1 + 2- 3 x 4- 5.

Â In this case we have five digits and four arithmetic operations.

Â And we would like to find an order of applying these four arithmetic

Â operations to maximize the value of this expression.

Â So when the order of operation is fixed, you do the following.

Â You take the first operation.

Â You take two adjusting digits, and you apply these operations.

Â For example, if the operation is multiplication, in this case, so

Â then two digits are 3 and 4.

Â So you multiply 3 and 4, you get 12, and you just replace 3 times 4 by 12.

Â You then take the next operation, apply it also, and replace two numbers and

Â the arithmetic sign by this result, until you proceed in a similar fashion.

Â In the end here, you get a single number.

Â And your goal is to find an order that guarantees that this

Â number is as large as possible.

Â 1:53

You can specify an order just by placing a set of parentheses in your expression.

Â For example, if you would like to apply all your four operations just

Â from left to right, you place the parentheses as follows.

Â In this particular case, we compute the results as follows.

Â So we first compute 1 + 2, this is 3.

Â We then subtract 3 from the results.

Â This gives us 0.

Â We then multiply the result by 4.

Â This is still 0.

Â And finally, we subtract 5.

Â So this gives us -5.

Â And this is actually non-optimal, because for example, there is a better order.

Â In this case, we first multiply 3 and 4, this gives us 12.

Â We then subtract 5, this gives us 7.

Â Then we go to compute the sum of 1 and 2, this gives us 3.

Â So when the final operation is subtraction, we subtract 7 from 3.

Â This gives us -4.

Â So in this case the order of applying operations was the following.

Â So we first compute the product of 3 and 4, so this is the first operation.

Â We then subtract 5.

Â This is the second operation.

Â We then compute the result of 1 + 2.

Â So this plus is the third operation, and

Â this minus is the fourth operation, the last one.

Â 3:20

It is not difficult to see that the optimal value in this case is equal to 6.

Â And it can be obtained as follows.

Â You first subtract 5 from 4.

Â This gives you -1.

Â You then multiply it by 3, and you get -3.

Â You then compute the sum of the first two digits.

Â This is 1 + 2, and that is equal to 3.

Â Finally you subtract -3 from 3.

Â This is the same as 3 + 3, it is equal to 6.

Â Well, you might find the result as follows,

Â you just go through all possible orders.

Â Let's see how many different orders are there.

Â Well, there are four arithmetic operations in this case, so

Â you can choose any of the four possible arithmetic operations to be the first one.

Â You can choose any of these three remaining operations to be the second one,

Â and you can select any of the two remaining operations to be the third one.

Â And the last one is unique, it is the only remaining operations.

Â So, in total, there are 4 by 3 by 2 by 1 different orders.

Â This is equal to 24, and you can just enumerate all of them, write them down,

Â compute an answer for each of these orderings and select the maximal value.

Â However, our method of going through all possible orderings does not scale well.

Â And this is why.

Â Consider the toy example shown on the slide.

Â In this case we have six digits and five arithmetic operations.

Â This example will require us to go through all possible 120 orderings.

Â 5:05

So just because there are five iterations, so any of five of them can be

Â the first one, any of the remaining four of them can be the second one, and so on.

Â So this is 5 by 4 by 3 by 2 by 1, which is equal to 120.

Â This is already not so easy to do this by hand.

Â I mean, to go through all possible such orderings.

Â Well, this is not easy, but we can teach a computer to do this, right?

Â So we can implement an algorithm that goes through all possible orderings.

Â However, in general, this algorithm will perform roughly n factorial steps,

Â where n is the number of arithmetic operations, for exactly the same reason.

Â If you have n arithmetic operations, then any of them can be the first one.

Â Any of the remaining n minus 1 operations can be the second one, and so on.

Â So this is n times n minus 1, times n minus 2, and so on.

Â This is equal n factorial, and n factorial is an extremely fastly growing function.

Â For example, 20 factorial already equals roughly 2 times 10 to the 18.

Â This means that if you implement such an algorithm, it will not be able to

Â compute the maximum value of an expression consisting of just 20 digits

Â in a reasonable time, even in one year, not to say about one second.

Â Which means, as usual, that we need another algorithm,

Â as you might well have guessed.

Â We will use dynamic programming to find, to design a more efficient algorithm.

Â In the meantime, you might want to check your intuition by trying

Â a few possible orderings to perform in this small expression,

Â and by using our in video quiz.

Â