# Algorithm {Triangle}

Hey, next problem from leetcode will be Triangle. Task description:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

```[
,
[3,4],
[6,5,7],
[4,1,8,3]
]
```

The minimum path sum from top to bottom is `11` (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Stop and think …

Judging to example we should go level by level and choose smallest “connected” value . Why I’ve written “connected” because if we have something like  that

```   [5,6,7],
[4,4,1,8]

```

we should choose 6,1 but not 5,4 because sum 6+1 < 5+4. OK interesting observation… So, what will be if we start from bottom to top ? We can choose smallest number and all will be correct. That is good, but how to check “connection”. In this situation we can use rule from Dynamic Programming(DP) (Store sum under i position of i-element from next level and min from i and i+1 element from stored values.) OK, lets go …

```    public int minimumTotal(@NotNull ListList<List<Integer>> triangle) {
if (triangle.size() == 0) return 0;
int[] cache = new int[triangle.size()];
List<Integer> bottom = triangle.get(triangle.size() - 1);
for (int i = 0; i < cache.length; i++) {
cache[i] = bottom.get(i);
}
int layer = cache.length - 2;
while (layer >= 0) {
List<Integer> list = triangle.get(layer);
for (int i = 0; i <= layer; i++) {
cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);
}
layer--;
}
return cache;
}
```

What I’ve written :

`int[] cache = new int[triangle.size()];`

Get last line(level) from triangle and put to cache

```List<Integer> bottom = triangle.get(triangle.size() - 1);
for (int i = 0; i < cache.length; i++) {
cache[i] = bottom.get(i);
}
```

after that start from next level and

Store sum under i position of i-element from next level and min from i and i+1 element from stored values.

```while (layer >= 0) {
List<Integer> list = triangle.get(layer);
for (int i = 0; i <= layer; i++) {
cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);
}
layer--;
}```

How this technique is working ? That is very easy, try to test our example :

• firstly we have put last level to cache , so, cache contains next values
`[4,1,8,3]`
• start loop from next level
`[6,5,7],`

i == 0, so, we store under 0-position  smallest sum  (6+4 or 6+1)

`cache[i] = list.get(i) + Math.min(cache[i], cache[i + 1]);`

next positions the same, OK after second line we will have our cache like next

`[7,6,8,3]`
• go to next level
`[3,4],`

cache will be next

`[9,9,8,3]`
• go to next level
``

cache will be next

```[11,9,8,3]
```

so, just return 0 position and that is all

`  return cache;`

So, we solved next task, that is good 🙂 Thanks!