Dynamic Programming Tutorial – Level 1 (Easy-Medium)- 1/2
WARNING : This tutorial is only for newbies who have no clue about what Dynamic Programming is and want to do well in it in programming contests. The tutorial is best if read from top to bottom, but you are free to skip to topics of your desire.
Ok..Hmmm… Dynamic Programming… Dynamic.. eh? What is the first thing that comes to your mind when you hear the word dynamic? Things moving…Things which are not static..Yes, those are precisely what dynamic means.
But now the catch…, Dynamic Programming has actually got nothing to do with those things. Dynamic Programming is just a fancy method of telling some normal guy(not a programmer) that you cheated while solving an algorithmic problem. Normally algorithmic problems involve searching/finding something which require some tedious work when a human does it but can be solved faster when a computer does it. But there are also some cases when a computer does it slowly, because of a slow algorithm(people normally call this brute force- meaning checking all possibilities blindly). This is normally exponential in the size of the input(which is very BAD).
For example, consider a list of elements – 5 3 8 1 2 10 23 . Find the number of distinct sets of elements such that the sum is say, 12. Now for this there could be many possibilities like { 8,3,1 } , {10,2} and so on. Finding the number of distinct sets in this example is easy. But what if the size of the input was like 100 or 1,000 or even 100,000. Then things could start getting messed up. Now try programming this using a computer. The simplest method would be to actually try all possible combinations like {5,3}, {5} ,{5,3,8} {8,1}. Doing this would be easy to code, but would take large number of unnecessary operations. Hence the time taken to execute the program would be enormous(when you actually code it, you will have to wait for nearly 4-5 mins. for the program to end..). The aim of dynamic programming is to make this time less than the actual time you take to say… DYNAMIC PROGRAMMING. 😛 .
This problem is formally known as the Subset-Sum Problem (duh… 😛 ) which an example of the Knapsack Problem(leave these for now..you will be familiar with them as you practice more and more…).
Now, a formal definition of Dynamic Programming..(actually a bit informal..:P)
-Trying to split a large problem into smaller problems such that the smaller problems are solved in the best way possible.
If the smaller problems are solved in the best way possible then, as the large problem is a collection of smaller problems, the larger problem can also be solved in the best way possible.
Now the aim of the problem is to solve the smaller problems. Like in the Subset-Sum problem, a smaller problem can be thought of finding the solution, say for a sum 1 or 2. Using this, an efficient solution for the main problem can be found out.
Another way to think of a dp solution is a recursion(a function which depends on results of smaller inputs..such as the following..)
Fibonacci – fib(n)=fib(n-1)+fib(n-2).
So if you can get the recursion for your dynamic programming problem, you are nearly done with your solution.. 😀 . Ok.. now coming towards the basics..
Try Solving this problem on codechef.. one of my favourites.. It’s pretty easy..
http://www.codechef.com/problems/SUMTRIAN
People learn more when they are taught the problem and then the solution, rather than the opposite. So solve the problem first(or atleast try to.. 😛 ) and please DO NOT look at the solution before trying it.
OK.. for those people who have solved it after hearing dynamic programming for the first time, CONGRATS..!!, even some of the world’s top programmers haven’t been able to achieve what you have done. But for others, don’t feel discouraged, after all the some of the world’s top programmers were also like you at some point.. 😛 . Ok coming to the solution.., this problem is a typical example of dynamic programming.
Remember the aim – Solve smaller sub-problems and use them to solve the large problems.
For the purpose of this tutorial, I am considering the following example…
5
1 7
6 3 4
One of the methods is the following. Start from the top.. (also known as the top-down approach). The longest path from 5 can be given as…
path(5) = 5+(max(path(1)+path(7))).
This means that if we solve the problem in row 2 i.e elements 1 and 7, we can automatically have the solution for row 1. Now each row, depends on the ones below it. Continuing this till we reach the last row, we solve the problem. In the last row, we just have individual elements and not paths. No need to specify a path for the row after the last one. The code snippet is shown below
int computedp(int a[105][105],int n,int row,int col)
{
if(row==n) return a[row][col];
return max(a[row][col]+computedp(a,n,row+1,col),a[row][col]+computedp(a,n,row+1,col+1));
}
Don’t just memorize dp solutions. It involves more of a technique than an algorithm. And like all techniques, it only gets better with practice.
Try solving the following problems. If you are a beginner in dp, then you may find these problems hard. But no worries, it happens to everyone. Read tutorials for these problems on any blog/forum/programming site and practise more. Hardwork is the key to Dynamic Programming and PS:- Just for the info.-300 problems from easy to hard makes you only an above average dynamic programmer.. 😛 . So people wanting to do well in programming contests, should focus on this. The difference between the world’s best competitive coders who come 1st and 2nd, is their skill in dynamic programming..!!
READ THE TUTORIALS FOR THESE PROBLEMS IF YOU CANNOT SOLVE THEM. Take your time .. it may take days to understand the following problems and implement them.
These are the easiest dp problems. So do not skip them, if you don’t know how to solve them.
http://www.codechef.com/problems/FCBARCA
http://www.codechef.com/problems/DBOY
http://codeforces.com/problemset/problem/166/E
http://codeforces.com/problemset/problem/363/B
http://codeforces.com/problemset/problem/118/D
http://codeforces.com/problemset/problem/159/D
http://www.spoj.com/problems/PARTY/-
The next part of this tutorial deals with some of the well known dp problems such as Longest Increasing Subsequence, Coin Denomination problem, Knapsack etc.
surajkrajan95 