Help me in SUMTRAIN

https://www.codechef.com/viewsolution/15038255

This is my attempt at solving SUMTRIAN.Please tell me where i am wrong.

Hey dear!

Firstly your approach to find max element in final row is wrong. Secondly, you are using greedy approach here i guess, which is wrong.

It is not necessary that you get maximum score by choosing maximum value every turn!!

Take this triangle-

1
1 5
1 1 5
100 1 5
1 1 1 5

If you go by choosing only maximum value, your final score will be 21, while you can get a better score. Remember, you can choose values which are only directly below or diagonally right to current one.

Can you give me a hint to solve this? This has been the hardest question i’ve encountered till now.

You need to learn dynamic programming for this. Thats your hint :slight_smile:

Thank you.I’ll learn it right away.