Unable to understand the required output for Sums in a Triangle problem

I have understood the problem statement in Sums in a Triangle problem except how the output 5 and 9 are calculated.

Could someone advise on how the output is calculated.

For first testCase it is 1+2+2=5 and for second one it’s 1+1+4+3=9… because of this rule mentioned in question…

on each path the next number is located on the row below, more precisely either directly below or below and one place to the right

The Q is that, you start from top of the given triangle. At each step you can either go to the element directly below your current on, or diagonally right to your current element. Score is sum of elements you walk on. You need to find the maximum score you can get.

How is 9 calculated?

1 
1 2 
4 1 2
2 3 1 1 

This is my pyramid. I have to come from top to base, i.e. 1st row to 4th row.

We start at 1. Score=1.

I decide to go just below (and not diagonally right). Now I am at 1 of {1,2}. Score=1+1=2.

Again I go directly below, Score is now 6.

Now i go diagonally right and make my score 9. This is the maximum score i can get.

This can be solved using dynamic programming, so I hope you can now give it a try :slight_smile:

simply use dynamic programming in this case don’t use the greedy approach otherwise it will give wa

simply iterate for triangles at a given time from the base going to the top then [0,0] index will store your answer

the triangles that you have to iterate are

4 store maximum sum in place of four ,i.e 7

2 3

then

1 store maximum sum in place of 1 that is 4

3 1

then

2 store maximum sum in place of 2 ,i.e 3

1 1

and go on repeating these steps until you reach the second row you will have your answer in (0,0);

So in the case of above triangle instead of

I decide to go just below (and not diagonally right). Now I am at 1 of {1,2}. Score=1+1=2

I could go one step right and add 2 so the score would be 1+2=3 instead of 1+1=2.

The way we did for the last line i.e.; 1+1+4+3 instead of 1+1+4+2.

You can, but remember, you cannot go to diagonally left element. Only bottom and diagonally right are allowed. You want to travel such that your final score is maximized. If you choose to go at 2, then irrespective of what you do, your score will be lower than 9.

Thank You got it

//