Subproblems and recurrence relation

Loading...

Do curso por Saint Petersburg State University

Competitive Programmer's Core Skills

1 classificação

Saint Petersburg State University

Competitive Programmer's Core Skills

1 classificação

During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Scala. We assume that you already know how to write simplest programs in one of these.

Na lição

Dynamic Programming

Dynamic programming is a powerful algorithmic paradigm with lots of applications in areas like optimisation, scheduling, planning, bioinformatics, and others. For this reason, it is not surprising that it is the most popular type of problems in competitive programming. A common feature of such problems is that a solution is usually easy to implement. This does not however mean that it is also easy to find a solution! Therefore, it is important to practice solving such problems. And this is exactly what we are going to do in this module!

Subproblems and recurrence relation8:52

Reconstructing a Solution9:02

Subproblems Revisited8:22

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov

[MUSIC]

Now, we are going to design a dynamic programming solution for

the so-called longest increase in subsequence problem.

In this problem we're given an array or just a sequence of n integers and

our goal is to find a subsequence inside the sequence which

is increasing as long as possible.

Now that it should not be contiguous.

So one example of the longest, of an increasing subsequence

in the sequence shown on this slide is 1, 3, 4, 6, 9.

So it is not difficult to check that it is indeed increasing, and

we will soon learn a way to convince ourselves that it is the longest possible.

Another longest increase in subsequence in this case is 2, 3, 4, 5, 8.

This shows in particular that an optimal solution for

this problem needs not to be unique.

So to start designing an algorithm for

this problem, let's try to analyze an optimal solution.

So consider a longest increasing subsequence and

its last two elements, z and x.

What can be said about z and x?

So first of all, we know that z must be smaller than x, okay?

So what is much more important for us in the following property?

The prefix of the longest increasing subsequence

shown here ending at the element z must be the longest

possible subsequence ending at this particular element.

Why is that?

Well, imagine that this is not the longest increasing subsequence ending at z.

This means that there is some other subsequence which is longer

than this prefix which ends at the element z.

But this would mean that we could take this longer

subsequence ending at z and append x to it.

This would give us a longer increasing subsequence

in the initial array than the one that we started with.

What we've just shown is that the longest increasing subsequence

problem possess the so-called optimal substructure property.

This means that in any longest increasing subsequence, any of its prefixes must

be also an optimal increasing subsequence ending at this particular element.

We have shown this by the so-called cut and paste trick, namely,

if this prefix is not optimal, then there is a longer prefix and

in this case we can cut this original prefix and paste a longer prefix.

And this would give us a longer increasing subsequence contradicting to

the fact that we started with an optimal solution.

And this leads us naturally to the following subproblems.

For all i starting from 0 to n minus 1, let's compute

the lengths of an optimal increasing subsequence ending at an element i.

As we've discussed previously, such a subsequence,

if it is not of length 1, it has some previous element j.

So in this case,

the length of an optimal increasing subsequence ending at the element

i is equal to the length of its prefix ending at some element j plus 1.

Corresponding to the fact that we append element i.

So this gives us the following recurrence relation.

So the solution for subproblem at i is equal to 1 plus

the maximum of all the solutions of all subproblems for

js where A[j] is smaller than A[i].

So we only go through all subproblems psi j i can

be appended to the solutions, okay?

So if there is no psi j, meaning that the set of all psi j is empty,

then in this case there are now j psi j A[j] is small as an A[i], and

in this case, clearly the solution to our subproblem is equal to 1.

Meaning that there is just 1 increasing subsequence ending at the element i,

and it is just the subsequence consisting of just this particular element, okay?

Also there is a base case when i is equal 0,

the solution to our subproblem is also equal to 1 and this case,

again our subsequence consists of just the zeros element.

We're now going to convert our recurrence relation into a recursive algorithm.

For this, we are going to use a table T such that T[i] is going to store

the value of a subproblem LIS(i).

The exact data structure behind the table T is not that important at this point.

It could be an array or a dictionary or a hash table or whatever.

So, it's usual before computing LIS(i),

we are going to check whether its value is already stored in the table.

If it is stored in the table, we'll return it immediately.

We only start computing it if it is not in the table yet.

And for computing it, we actually follow our recurrence relation.

So we first initialize it to 1, just to reflect the fact that we always

have at least one increasing subsequence ending at the element i,

it is the subsequence consisting of just element i.

Then we go through all js that are smaller than i,

such that A[j] is smaller than A[i].

And we check whether appending i to an optimal increasing subsequence

ending in j, whether it gives us a better solution than we currently have.

If it gives us a better solution, then we update our current solution.

Finally, we store the result of T[i], and as a result of the whole algorithm,

we need to return the maximum overall i of LIS[i].

This is just because we don't know where

the optimal increasing subsequence ends, okay?

The running time of this algorithm is quadratic.

And this is just because there are n serious recursive calls.

By a serious recursive call, I mean a call which is not just a table look-up.

There are at most n of them, just because each time when there is a serious call,

we store its value into our table.

And the running time needed to compute this value is also proportional to n.

Overall, this gives us n squared operations, okay?

Then, one can notice that what we need to store in

the table are all solutions to our subproblems.

They're indexed by integers from 0 to n- 1,

and in fact, these are consecutive integers.

This suggests that we can use an array to implement our table T.

And in fact, we can actually fill in this array

just in a straightforward fashion, I'm sorry.

So we're going to fill in these array iteratively instead of recursively.

So for this we first initialize this array, and

then in a single loop going from left to right, we fill in

this array with values using our previous recursive definition.

What is important to note here is that each time when we compute T[i],

all the previous T of js, for js less than i are already computed, okay?

So the running time of this algorithm is also quadratic just

because it consists of two nested for loops.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play