Skip to main content

Dynamic Programming

 Dynamic Programming is one of the most popular techniques in competitive programming and a powerful algorithm design technique. This handout aims to give a brief introduction to Dynamic Programming.

Optimization Algorithms
An algorithm is a set of steps to perform a certain procedure and reach a certain end goal. In particular, the problems we are going to be looking at in this handout are going to be optimization problems - problems that aim at minimising or maximising something, finding a shortest path, or trying to find the best way to do something.

Greedy Algorithms
Greedy algorithms are used to solve optimisation problems which try to maximise short term goals by making decisions that seem to be optimal in the current scenario but may not be ideal in the long run. 

Example 1(Activity Selection Problem) : On a certain day, there are $n$ events that you would like to attend. Each of these events has a start time $s_i$ and a finish time $f_i$. Some of these events may overlap and you are only allowed to attend events with no overlap. Provide an efficient algorithm that lets you maximise the number of events you attend (completely).

Walkthrough : Note that we haven't introduced the notion of an efficient algorithm. The idea is that if we allowed any algorithm, we could have just bruteforced through each of the $2^n$ possibilities and seen which works with maximum number of events. However this is exponential in the number of events and is therefore very inefficient. Instead, we need an algorithm that can at most require a number of steps that is polynomial in $n$.
  1. Work out why a greedy algorithm that picks the shortest event  followed by the next shortest event that can still be picked (and so on) does not work.
  2. Show that a greedy algorithm that tries to pick the event with minimum $s_i$ (that can be picked) at any point does not work.
  3. Prove that the previous idea with $s_i$ replaced with $f_i$ works.
Example 2(Weighted Activity Selection Problem) : This is the same as the previous problem, except now each event has a value $v_i$ and your aim instead is to maximise the sum of the values of the events you attended.

Walkthrough(or not?) : Show that the greedy algorithm in the previous example fails here.

Note that it is infact not possible to solve this problem with a greedy algorithm. To solve it, we are going to have to expand our tool kit and learn the technique of Dynamic Programming.

Dynamic Programming
Dynamic Programming is a very powerful algorithmic technique used to solve optimization problems which is seen a lot in computer science. It is essentially an improvement to simple recursion. It aims at solving problems by dividing them into smaller sub-problems and then combining results of various sub-problems to get the final result.
The technique was invented by Richard Bellman. Here's an interesting story on the origin of dynamic programming. 

Bellman explained that he invented the name dynamic programming to hide the fact that he was doing mathematical research. He was working at a place called RAND under a secretary who had a pathological fear and hatred for the term research.

So he settled on the name dynamic programming because it would be difficult to give a bad meaning to it. It was something nobody would object to.

Long story short, the name sounded cool.

Dynamic programming can also be thought of as a Careful Brute Force, which seems quite odd but we'll see soon as to why exactly this makes sense.
As an algorithm, dynamic programming usually runs through all possible outcomes of a certain event but does so in a careful way that avoids exponential time.

Lets do an example, which is not technically an optimization problem but illustrates the ideas of dynamic programming well.

Example : You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Walkthrough : This problem is quite easy, all we need to find is a pattern in the number of ways for increasing $n$.
  1. If you haven't already done this, figure out the number of ways for small $n$ until you can see what's happening.
  2. Show that the pattern you found is infact true.
If you solved the problem correctly, you would have noticed that there is a recurrence relation (the Fibonacci) using which we can figure out the required number of ways. Here is how the code for this might look : 

While this definitely works, there is a major problem in the code written above. The problem is that we end up performing the same computations a large number of times since we do not remember the values we had already calculated earlier.
Notice that $f(2)$ is being calculated once on the left and once on the right - which slows down our program a lot.
To avoid this we use the technique of memoization. The idea is that we remember the answers to sub-problems  we have already solved rather than re-calculating them. This brings in the \emph{careful} nature of the brute-force.

A solution using memoization for the above problem may look something like the below:
To master the skill of dynamic programming, there are 5 key steps that we should remember
  1. Define the subproblems : In the above problem subproblems are essentially climbing a smaller number of stairs.
  2. Guess your first move : This is important! When we do not know how to start, we should try every possibility. In the above problem, we did not know whether the first move was a single step or two and we therefore consider both cases and build a recurrence on that guess.
  3. Find the recurrence relation : a relation between different subproblems. This is essentially what allows us to solve the problem. In the above example we had $$f(n) = f(n-1) + f(n-2)$$ And it is this recurrence that allows us to calculate the number of required ways.
  4. Recurse and memoize : We write the code and remember to remember!
  5. Solve original problem : At the end we calculate the function for the particular value of variables that we were desiring
Let us now discuss 2 more cool problems on dynamic programming and see how each of our key steps applies to solving the problem.

Example : Let's say you are given a rod of length $n$ metres. The rod is quite valuable and you would like to sell it in the market. Different lengths of the rod can be sold for different prices and you would like to maximise your earning. To do this, you cut your rod into multiple (possibly just one) parts and sell each of them in the market. Find an efficient algorithm that gives you the maximum earning you can achieve by selling the rod.

To be more precise, you are given an array of $n$ integers, representing the price of an $i$ metre rod in the market with $0<i\leq n$. Determine the maximum value obtainable by cutting up a rod of length $n$ metres and selling the pieces.

Walkthrough : 
  1. What seem to be the natural subproblems for the given problem?
  2. We do not know where to first cut the rod - it could be anywhere, right? Make a guess on what we should first guess.
  3. If your guess and choice of subproblems was correct, you should be quite close. You just want to see which of the subproblems you ended up at after your initial guess is optimal. In a sense you're looking to find the maximum of a certain set of values.
If you like to code, you can now try to code this up!

Solution : Let the value of a rod of length $k$ metres be $a_k$ and $f(k)$ denote the best possible price obtainable by selling a rod of length $k$ metres. Our recurrence is $$f(n) = \text{max}_{i=1}^{n} (a_i + f(n-i))$$


Example : Given a grid of size $m\times n$, let us assume you are starting at $(1, 1)$ and your goal is to reach $(m, n)$. At any instance, if you are on $(x, y)$, you can either go to $(x, y + 1)$ or $(x + 1, y)$. Now consider if some obstacles are added to the grids. How many unique paths would there be?

Who said dynamic programming is limited to just one dimension? Here we use our DP approach with 2 different parameters. 

Walkthrough : 
  1. We ask the same questions again, what seem to be the natural subproblems for the given problem?
  2. We do not know what the last move was - we could have come from the left or from below, right? Make a guess on what we should last guess.
  3. The problem is now somewhat similar to original $n$ stairs problem we had tried. The only problem is that we have a couple of obstacles in our way. Figure out a neat way to add up the cases of each possibility of our guess while keeping in mind that the cell we're currently considering may be blocked.
Again, if you like to code, you can now try to code this up!

Solution : Let $f(a,b)$ denote the number of ways to reach cell $(a,b)$ from $(1,1)$. Our recurrence is
$$f(a,b) = \begin{cases}f(a-1,b) + f(a,b-1) & \text{if (a,b) is not blocked} \\ 0 & \text{otherwise} \end{cases}$$ 

Problems
Problem 1 : Try solving Example 1.2 with the technique of dynamic programming

Problem 2 : The Longest Increasing Subsequence problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for $\{10, 22, 9, 33, 21, 50, 41, 60, 80\}$ is $6$ and the LIS is $\{10, 22, 33, 50, 60, 80\}$. 

Problem 3 : The Longest Common Subsequence (LCS) problem is finding the longest subsequence present in given two sequences in the same order, i.e., find the longest sequence which can be obtained from the first original sequence by deleting some items and from the second original sequence by deleting other items.



Post by Rushil Mathur.

About the guest blogger: Rushil is an 11th grader from Mumbai. He’s been doing olympiad math for over 3 years now and he absolutely loves combinatorics. Apart from maths, he likes competitive programming and is always up for a chess match. 
Rushil is a 2022 INMO Awardee and a part of the Sophie Fellowship program.  He also won a bronze at the INOI 2022.


Post set up and modified by Pranav Choudhary.

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig