Dynamic Programming or Memoization is a well known technique for optimization. It is just a method that remembers your previously calculated results and stores it somewhere so that when time comes you can use it again.
Just to begin with, a straightforward example of Memoization is calculation of Factorials. When we calculate Factorial of 5, i.e.
5! = 1*2*3*4*5 = 120
Now when you're asked to calculate Factorial of 6, a normal human being wouldn't go on like 1*2*3*4*5*6 rather he would think that "Well, I just calculated upto 5! why not simply multiply 6 to the answer of 5! " This is exactly what we are going to make our computers to do.
So, How do I make computer to remember pre-calculated results?
Answer is as simple as the question, just store them at a particular location in any array/list/vector.
Have a look at this simple Python implementation for memoized Factorial.
Line #2: simply creates a list of 101 members starting from remember[0] to remember[100]
Line #3: initializing remember[0], since 0! = 1
Line #4 & #5: if we already calculated for that number simply return the value stored at that position.
Line #7: this is the recursive logic
Line #8: storing calculated result at correct position in remember array
But problems aren't as easy as such we dealt till now. You might not be able to incorporate this idea in other examples. Lets have a look at a question where we can use Memoization/DP.
Q: We have a triangle of numbers, starting from top of a triangle we are allowed to move exactly below or right-to-exactly-below (see example). Reaching till the last row of triangle we have to find out which way got you the largest sum.
eg:
3
2 5
6 4 1
In above triangle, we start with 3 and according to the given conditions we can go either to 2 or 5, if we go towards 2 we can either go to 6 or 4 and if we went towards 5, we could either go to 4 or 1. So, we got
Path #1: 3->2->6 Sum is 3+2+6 = 11
Path #2: 3->2->4 Sum is 3+2+4 = 9
Path #3: 3->5->4 Sum is 3+5+4 = 12
Path #4: 3->5->1 Sum is 3+5+1 = 9
One with the maximum sum is Path 3, we simply have to find this sum i.e. 12
(Few questions around web that are exactly similar and from where I got idea to write down this article are Codechef's SUMTRAIN, Problem 18 and 67 on ProjectEuler.net)
Normal guy would simply go through all the possible paths and find maximum sum, but that would definitely eat up a lot of time. So here we jump into Memoization or DP. We'll store the last maximum sum we found till now at each step. You might feel "what the hell is he talking", so lets take our above example.
First of all lets assign it to a 2D array like this.
a[0][0]
a[1][0] a[1][1]
a[2][0] a[2][1] a[2][2]
Hence a[0][0] = 3, a[1][0] = 2, a[1][1] = 5, .... and so on.
Starting from a[0][0], we can move to a[1][0] or a[1][1]. So we can arrive to a[1][0] only from a[0][0]. Lets store the sum till now, store 3+2 = 5 into a[1][0], similarly we can arrive at position a[1][1] from a[0][0] only, so store 3+5 = 8 into a[1][1].
Now moving to a[2][0], we can arrive here only from a[1][0], so store 5+6 = 11 into a[2][0]. Here comes a[2][1], we can arrive a[2][1] from either a[1][0] or a[1][1], since we want sum to be max we'll choose the one with greater value i.e. a[1][1] = 8. Store 8+4 in a[2][1]. Similarly a[2][2] can only reached from a[1][1], so store 8+1 in a[2][2].
Now our array looks like this.
3
5 8
11 12 9
Maximum of the last row of this array is our answer. Viola its done. We found it without going through all different paths. And believe me its a much better optimization if we take even larger triangles and compare the time taken.
Now we simply have to implement this in code. I'll do it in Python coz its easily readable.
Line #2: n is number of rows in our triangle.
Line #3 & #4: creating an empty lists, read how lists work in python
Line #5 to #7: taking input in the form of 2D array.
for i in xrange(3) means it'll go through 0,1 and 2.
Line #8 to #18 is our logic implementation:
Line #10: This condition is for a[1][0], a[2][0] etc where we can only arrive from just above element.
Line #12: This condition is for a[1][1], a[2][2] etc where we can only arrive from element present at diagonal to us.
Line #19: prints out the max of the last row of our array.
Rest is self understood.
Try out in your own programming language and verify the results.
Got a burning question you wanna get answered? Leave it in the comments or just leave a thanking comment if this post helped you :-)
Happy Coding.
Just to begin with, a straightforward example of Memoization is calculation of Factorials. When we calculate Factorial of 5, i.e.
5! = 1*2*3*4*5 = 120
Now when you're asked to calculate Factorial of 6, a normal human being wouldn't go on like 1*2*3*4*5*6 rather he would think that "Well, I just calculated upto 5! why not simply multiply 6 to the answer of 5! " This is exactly what we are going to make our computers to do.
So, How do I make computer to remember pre-calculated results?
Answer is as simple as the question, just store them at a particular location in any array/list/vector.
Have a look at this simple Python implementation for memoized Factorial.
Line #2: simply creates a list of 101 members starting from remember[0] to remember[100]
Line #3: initializing remember[0], since 0! = 1
Line #4 & #5: if we already calculated for that number simply return the value stored at that position.
Line #7: this is the recursive logic
Line #8: storing calculated result at correct position in remember array
But problems aren't as easy as such we dealt till now. You might not be able to incorporate this idea in other examples. Lets have a look at a question where we can use Memoization/DP.
Q: We have a triangle of numbers, starting from top of a triangle we are allowed to move exactly below or right-to-exactly-below (see example). Reaching till the last row of triangle we have to find out which way got you the largest sum.
eg:
3
2 5
6 4 1
In above triangle, we start with 3 and according to the given conditions we can go either to 2 or 5, if we go towards 2 we can either go to 6 or 4 and if we went towards 5, we could either go to 4 or 1. So, we got
Path #1: 3->2->6 Sum is 3+2+6 = 11
Path #2: 3->2->4 Sum is 3+2+4 = 9
Path #3: 3->5->4 Sum is 3+5+4 = 12
Path #4: 3->5->1 Sum is 3+5+1 = 9
One with the maximum sum is Path 3, we simply have to find this sum i.e. 12
(Few questions around web that are exactly similar and from where I got idea to write down this article are Codechef's SUMTRAIN, Problem 18 and 67 on ProjectEuler.net)
Normal guy would simply go through all the possible paths and find maximum sum, but that would definitely eat up a lot of time. So here we jump into Memoization or DP. We'll store the last maximum sum we found till now at each step. You might feel "what the hell is he talking", so lets take our above example.
First of all lets assign it to a 2D array like this.
a[0][0]
a[1][0] a[1][1]
a[2][0] a[2][1] a[2][2]
Hence a[0][0] = 3, a[1][0] = 2, a[1][1] = 5, .... and so on.
Starting from a[0][0], we can move to a[1][0] or a[1][1]. So we can arrive to a[1][0] only from a[0][0]. Lets store the sum till now, store 3+2 = 5 into a[1][0], similarly we can arrive at position a[1][1] from a[0][0] only, so store 3+5 = 8 into a[1][1].
Now moving to a[2][0], we can arrive here only from a[1][0], so store 5+6 = 11 into a[2][0]. Here comes a[2][1], we can arrive a[2][1] from either a[1][0] or a[1][1], since we want sum to be max we'll choose the one with greater value i.e. a[1][1] = 8. Store 8+4 in a[2][1]. Similarly a[2][2] can only reached from a[1][1], so store 8+1 in a[2][2].
Now our array looks like this.
3
5 8
11 12 9
Maximum of the last row of this array is our answer. Viola its done. We found it without going through all different paths. And believe me its a much better optimization if we take even larger triangles and compare the time taken.
Now we simply have to implement this in code. I'll do it in Python coz its easily readable.
Line #2: n is number of rows in our triangle.
Line #3 & #4: creating an empty lists, read how lists work in python
Line #5 to #7: taking input in the form of 2D array.
for i in xrange(3) means it'll go through 0,1 and 2.
Line #8 to #18 is our logic implementation:
Line #10: This condition is for a[1][0], a[2][0] etc where we can only arrive from just above element.
Line #12: This condition is for a[1][1], a[2][2] etc where we can only arrive from element present at diagonal to us.
Line #19: prints out the max of the last row of our array.
Rest is self understood.
Try out in your own programming language and verify the results.
Got a burning question you wanna get answered? Leave it in the comments or just leave a thanking comment if this post helped you :-)
Happy Coding.
