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
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
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
Lol why me? But anyways, I gladly accept any thanks given to me