How to solve SUMTRIAN problem?

general
1

Please tell me -How to solve SUMTRIAN problem?

2

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
3

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:

4

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

1 Like
5

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

6

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

1 Like
7

Tnq @inovation123 and @vijju123

8

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

9

This post was flagged by the community and is temporarily hidden.

10

Why was this post flagged?