Subproblems

Loading...

Del curso dictado por University of California San Diego

Algorithmic Toolbox

4364 calificaciones

University of California San Diego

Algorithmic Toolbox

4364 calificaciones

Curso 1 de 6 en SpecializationData Structures and Algorithms

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

De la lección

Dynamic Programming 2

In this module, we continue practicing implementing dynamic programming solutions.

Problem Overview7:01

Subproblems6:57

Reconstructing a Solution8:56

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

As usual, we start designing our dynamic program in algorithm

by defining a subproblem in a way that allows us to solve

a subproblem by solving smaller sub subproblem.

As we said already, this is probably the most important step

in designing dynamic programming solutions.

So before doing this, we define our problem formally.

So the input consists of n digits.

d1, d2, and so on, dn.

And then -1 operations between them, which we call op1, op2, and so on, opn.

Each operation is either summation, subtraction, or multiplication.

And our goal is to find an order of applying these operations so

that the value of the resulting expression is maximized.

As we discussed already,

we can specify this order just by placing parentheses into our expression.

We start building our intuition by reconsidering our toy example.

So assume that the multiplication is the last operation in some optimal ordering

in an ordering leading to an optimal value in this toy example.

Well this means that in this expression we already have to pairs of parentheses.

And our goal is to parenthesize the initial sub-expression and

the second sub-expression, so as to maximize the value.

This means that it would be good for us to know what is an optimal value for

the first subexpression and the second subexpression, right?

And in general if you have an expression and

if you select a realistic operation, which is the last one,

then it splits your initial expression into two subexpressions, right?

And for both of them it would be good to know an optimal value.

And, in turn, each of these two subexpressions are split into two

sub subexpressions by the last arithmetic operations, and so on.

So this suggests Very good problem in our case would be find an optimal value for

any subexpression or former initial expression.

So we've just realized that it would be good to know the optimal values for

all subexpressions of our initial expression.

What do we mean however, by saying optimal values for all subexpressions?

Assume for example that we need to compute the optimal, the maximal value for

the sum of two subexpressions, subexpression one and subexpression two.

Well this obviously means that we would like this subexpression to be

as large as possible and this subexpression to be as large as possible.

If on the other hand we would like to compute

the maximum value of subexpression one minus subexpression two.

Well this means that we would like subexpression one to be

as large as possible while we would like the value of subexpression two

to be as small as possible, right?

Just because we compute subexpression one minus subexpression two.

This suggests that knowing just the maximal value for

each subexpression would not be enough.

And this usually happens when designing a dynamic programming solution.

This also suggests that, instead of computing just maximal,

we will maintain what is the maximum value and

the minimum possible value for each subexpression.

Let's illustrate this reasoning once again with our previous toy example.

So in this case we are maximizing the product of two small subexpressions.

In this case these two subexpressions, so

small, that it is not difficult to compute their minimal and maximal values.

For example, for subexpression 5- 8 + 7,

the minimum value is- 10 and the maximal value is 4, right?

At the same time, for the second subexpression,

(4-(8+9)), the minimum value is- 13, while the maximum value is 5, right?

Now we would like to parenthesis both subexpressions, so

that their product is maximal.

Well it is not difficult to see, that in this case the optimal way to do this is

to take the minimal values of both sub expressions, right?

So this will give us- 10 multiplied by -13, which is equal to 130.

Right?

Which is much larger than the product of the maximum

values of these two sub expressions which is 4 by 5, which is 20 in turn.

Okay, we are now ready to write down the recurrent relation for our subproblems.

Before this, let's formally define E of ij to be the subexpression of our initial

expression resulting by taking digits from i to j and all operations between them.

Then our goal is to compute the maximum value of the subexpression which we denote

by capital M(i,j) and the minimum value of the sub expression denoted by m(i,j).

Okay, can you see that our initial subexpression from I to J and

assumes that we would like to compute one of the extreme

values of the subexpression and implies there is a minimum or the maximum.

Well we know that in many ordering for this subexpression there is some

last operation, say okay so this separation splits our

initial subexpression into two sub subexpression namely,

subexpression i, k and subexpression k plus 1j.

Right?

To compute the maximum value, we just go through all possible such case,

from i to j- 1, and through all possible extreme values for two subexpressions.

I mean, either we apply operation k to the maximum values of these two

subexpressions or we apply operation K to minimum value,

the minimum values of these two subexpressions.

Or we apply it to the maximum value of one subexpression and

the minimum value of another or vice versa.

To compute the maximum value of sub expression i j,

we just select the maximum among all these possibilities.

While to compute it's minimum value,

we simply select the minimum among all such possibilities.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play