I’ve been trying to understand the issue of sumtrian problem. I reread the problem, however i’m unable to understand the relation between the input and the output.
Plz someone explain me the scenario. The problem link is given below.
Basically we are trying to figure out the path from top row to the bottom row such that the sum of numbers along this path is maximum(Keeping in mind the conditions remains satisfied, move down or down right). Rather than to print the path, here it is asked to just output the sum of numbers along this path.
for example ::
1
2 1
1 2 3
Here the possible paths from top to bottom along with their sum are 1-2-1(4), 1-2-2(5), 1-1-2(4), 1-1-3(5). Among the given options we will be outputting to the user the max value i.e. 5.
Detailed explanation of the DP used here is given in the link .
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];