Could anyone help me on this
http://www.codechef.com/viewsolution/1838442
Seems your algorithm is wrong.
My idea:
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];