https://www.codechef.com/viewsolution/19621543

It does have an exit command at the end.

I would be surprised if it was memory usage as I’ve seen similar (100+) memory usage for C# solutions.

Not too much info pls, just a few hints…

https://www.codechef.com/viewsolution/19621543

It does have an exit command at the end.

I would be surprised if it was memory usage as I’ve seen similar (100+) memory usage for C# solutions.

Not too much info pls, just a few hints…

My idea of this problem:

let’s say starting row x = 0, y = 0 then → next row (either go down directly (x + 1, y) or down right (x + 1, y + 1)), after go to the final row, you need to figure out the max sum.

My DP Solution:

generate a 2D DP array, dp[i][j] save till current row, the max sum, so the answer is the max of the final row.

to update dp[i][j], needs previous max sum from top dp[i-1][j] or top left dp[i-1][j-1], plus current g[i][j]

so: dp[i][j] += g[i][j] + Math.max(dp[i - 1][j], dp[i - 1][j - 1]);

case condition, first col j == 0, only from dp[i-1][j], top left is out of bound

so dp[i][j] += g[i][j] + dp[i - 1][j];