How to solve SUMTRIAN problem?

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! :slight_smile:

good thing about this problem is dp formulation is quite intuitive and thats why problem belongs to beginner category :slight_smile:

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 :stuck_out_tongue: )

ya I agree problem setter has done a commendable job to help beginners to get a glimpse of dp

1 Like

Tnq @inovation123 and @vijju123

Lol why me? But anyways, I gladly accept any thanks given to me :stuck_out_tongue: