what are the prerequisite to solve this problem …
I mean what are the concepts should I know …
here is the link for the problem…
This problem needs to be solved by Dynamic Programming. However the question is an easy one and you dont need any knowledge of DP to solve it. The important thing to realize here is that the longest path from top to bottom is also the longest path from bottom to top.
First step that i would suggest is that you write a simple recursive solution for the question. The recursive relation will be something like func(i, j) = arr[i][j] + max( func(i+1,j) , func(i+1,j+1) ).Here arr[i][j] is distance given in the triangle and func( i,j) gives the length of the longest path from bottom to (i,j). The problem with a recursive solution is that it will time out since time required will be 2^(n) which will not get accepted. Now you will need to convert this into an iterative code.
Now to make this conversion you can start from the second last layer and do dist[i][j] = arr[i][j] + max( arr[i+1][j], arr[i+1][j+1]). The 2D array dist stores longest distance from bottom to (i,j). you can this is valid for second last layer directly from the recursive equation. Now to compute subsequent layers you can use the relation dist[i][j] = arr[i][j] + max( dist[i+1][j], dist[i+1][j+1]). You can prove it yourself. Actual solution will be something like compute 2nd last laer, the 3rd last, the 4th last until you reach the top. dist[0][0] will store the length of the longest path from top to bottom.
This is just a rough idea of how the code works I am leaving it upto you to try and implement the logic. If you have further doubts , feel free to ask.
2 Likes
Good explanation. Expecting more from you.
Can you help me with this: http://discuss.codechef.com/questions/41444/tle-for-sums-in-a-triangle-with-memoization ?
I used recursion with memoization as said in the tutorial. But it gives me a TLE 
could you tell me what more do you need. If you still have doubts then just have a look at someones code. The main logic is barely 5-6 lines and is easy to understand once you try it out manually on small examples
1 Like
Hi vineet. The problems with recursion is that it involves a lot of overhead in pushing and popping values from stack during each function call. Although the difference is not very large, the time limit for the problem is strict enough to allow only allow iterative solutions to pass. although recursion makes coding a lot easier, it comes at the cost of time.
@kcahdog i followed your algorithm,yet i ended up on WA.I tried my own testcases, given testcases and the results are correct .Can you please help me find where I’ve gone wrong ?
Link to my solution : https://www.codechef.com/viewsolution/16733062