Please tell me -How to solve SUMTRIAN problem?
This is a cakewalk. You can use recursion but it will give TLE. You might now have guessed that DP can be a saviour and is indeed as always. DP formulation is very easy.
Lets say that dp[i][j] represents total sum we can collect by reaching cell i,j
Answer would be max of all possible dp[i][j] which would be in last row as all entries are positive
Now dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j-1]) as from any cell we can go either bottom cell or bottom right cell only
Beware of large input and you will get a green tick.
My submission for refernce
https://www.codechef.com/viewsolution/13036307
Hope it helps
2 Likes
True. DP is the way to go here. Handling large input is to be taken care of, so python or java for such problems would be nice I guess. Good explanation! 
good thing about this problem is dp formulation is quite intuitive and thats why problem belongs to beginner category
1 Like
Its good for beginners in dp. It actually gave me confidence when I cracked the dp table (didn’t attempt it tho, numbers out of long long range make me lazy 
)
ya I agree problem setter has done a commendable job to help beginners to get a glimpse of dp
1 Like
Lol why me? But anyways, I gladly accept any thanks given to me