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

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