The problem I will be solving is Sums in a Triangle .The problem basically asking us to find the maximum sum in a single path from the given triangle and path can be 1st rows number+ next rows number from the same column or current column+1 and then next row and so on.
At a glance the solution that comes in mind is that we'll take the number from first row and then from next row we'll take the number from same column or current column+1 depending on which one is maximum. But this is a greedy approach and if you see the 2nd test case, you'll see that this approach doesn't give us the correct answer. the second test case:
If you notice I'm running the outer loop till 2 , though I've take input from 1. This is because, we are storing the result in a[i-1][j] by adding it with the maximum of a[i][j] and a[i][j+1], if we run loop till 1 when i=1, we'll have a[0][j] where we don't have any value. And then in the inner loop we're just checking which one is maximum and adding it with the previous rows number, exactly what we did in the table earlier. And at the end we are printing the number from first row, because that's where we get the result duh! (remember the table ;) ).
The whole code looks like this:
And the reason it is a dp problem is because we could divide it in sub problem and at the end got result by solving those sub problems.
At a glance the solution that comes in mind is that we'll take the number from first row and then from next row we'll take the number from same column or current column+1 depending on which one is maximum. But this is a greedy approach and if you see the 2nd test case, you'll see that this approach doesn't give us the correct answer. the second test case:
1
1 2
4 1 2
2 3 1 1
Here if we take 1 then if we follow greedy approach and take
2 from 2nd row because that is the maximum between 1 and 2, then from 3rd row
we can't take 4. Because the constraints says the path can be the below row and
same column or current column+1(that means one place to the right) so, the
answer we'll get in this approach is 6 which is wrong.
But if we use bottom up approach we'll get correct answer. In bottom up approach we'll divide the triangle into smaller triangles. And as the name suggest we'll start from the bottom(last row). So, if we draw the the triangle in row and column:
If we start from row 4 column 1 and row 4 column 2, between these two if we add 3 with 4 we'll get the maximum number, so the answer for row 3 column 1 is 7. And if we follow same method we'll get answer 4 for row 3 column 2. Calculating all the rows we'll get a triangle like below:
We can see at the 1st row we get the result. In the beginning I've said in bottom up approach we'll divide it in smaller triangle and that's what we did. We took row 4 column 1, row 4 column 2 and row 3 column 1 as a smaller triangle and that gave us the answer for row 3 column 1. And that's how we got the result for other rows also.
Now let's get to the coding part. as we are dealing with rows and columns ,it is obvious that we have to take a 2d array and and take input.
Now let's implement the bottom up approach. What we are doing is we are starting from the last row and checking maximum value of two column of that row till the column number is one less than the row number:
The whole code looks like this:
