= 3628800Usually, problems in competitive programming contests are not as easy as this.
Let’s take one of the questions where we make use of Memoization.
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.
For example:32 56 4 1In the 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 have 4 paths in total.
Path #1: 3 -> 2 -> 6 Sum is 3+2+6 = 11Path #2: 3 -> 2 -> 4 Sum is 3+2+4 = 9Path #3: 3 -> 5 -> 4 Sum is 3+5+4 = 12Path #4: 3 -> 5 -> 1 Sum is 3+5+1 = 9One with the maximum sum is Path #3, we simply have to find this sum i.
e.
12(Few questions around the web that are exactly similar and from where I got the idea to write down this article are Codechef’s SUMTRAIN, Problem 18 on ProjectEuler.
net)Normally, we would go through all possible paths and find the maximum sum, but that would definitely eat up a lot of time.
It would result in Exponential Time Complexity.
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!”.
Let’s take the example above.
First of all, let's 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 the 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 the sum to be maximum we’ll choose the one with greater value i.
e.
a[1][1] = 8.
Store 8+4 = 12 in a[2][1].
Similarly a[2][2] can only be reached from a[1][1], so store 8+1 = 9 in a[2][2].
Now our array looks like this.
35 811 12 9Maximum of the last row of this array is our answer.
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 because it is more readable.
def sum_triangle(): n = input() a = [] subA = [] for i in xrange(n): subA = map(int,raw_input().
split()) a.
append(subA) for i in xrange(1,n): for j in xrange(i+1): if j == 0: a[i][j] = a[i-1][j] + a[i][j] elif j == i: a[i][j] = a[i-1][j-1] + a[i][j] else: if a[i-1][j] > a[i-1][j-1]: a[i][j] = a[i-1][j] + a[i][j] else: a[i][j] = a[i-1][j-1] + a[i][j] print max(a[n-1])sum_triangle()Let’s analyze the above code:Line #2: n is number of rows in our triangle.
Line #3 & #4: creating an empty list.
Line #5 to #7: taking input in the form of 2D array.
for i in range(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] .
a[n][0] where we can only arrive from just above the element.
Line #12: This condition is for a[1][1], a[2][2] .
a[n][n] where we can only arrive from element present at the diagonal edge of the triangle.
Line #19: Prints out the max of the last row of our array.
Try it out in your own programming language and verify the results.
.. More details