why is everyone using 2 d array…wasting space…acc to me ,my code is working for a number of test cases that i have tried…but still it shows the wrong answer…i have just done the dynamic programming approach but in top-bottom manner. …and by comparing the last row’s adjacent elements and thus selecting the maximum…we get the largest sum…
Can you share the link to your submission? In that case, someone can help you!
1 Like
- try this test case:
- 1
- 99
- 99
- 99 99
- 99 99 99
- 99 99 99 99…
- you can fill this test case by writing a program to print 4851 99’s and redirect it to a file
- you can do this in this way:
- for(i=1;i<=4851;i++)
-
printf("99 "); - and compile this program and run it like this ./a.out > i
- now open i file and enter 1 and 99 for number of test cases and number of rows
- now compile your original program and execute like this ./a.out < i
- correct answer is :9702 but you are getting wrong answer
- if any doubts comment below
2 Likes
Invalid solution Id
Main 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];