how to approach for problem -sums in a triangle in codechef link-> https://www.codechef.com/problems/SUMTRIAN

dp codechef sumtrian

manish_kumar
Manish Kumar Savita
manish_kumar

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

nky_007
nky_007 23:15, Mar 25
Narendra Kumar Yadav

It's pretty straightforward (simple dp approach).Make another 2D matrix and initialize its value as 0 then for every cell store the value as "max of upper cell and upper left cell  + current cell value" and so on.
For example: 

        Original matrix :                    New Matrix :

                  1                                       0                            1                           1                    1

                   2 1                                   0 0         ->            0 0          ->           3 2      ->        3 2

                   1 2 3                                0 0 0                     0 0 0                      0 0 0              4 5 5 

  Now find the largest value in the last row, which is your answer as in this case ( ans = 5).




Please make sure the answer is not too short
3 Upvotes
Comments
No Comments yet