Help me in SUMTRAIN

help
dynamic-programming
wa

#1

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

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


#2

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.


#3

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


#4

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


#5

Thank you.I’ll learn it right away.