# 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

```[
[2],
[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[0];
}
```

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
`[2]`

cache will be next

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

so, just return 0 position and that is all

`  return cache[0];`

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

August 1, 2024

### Revolutionizing Your Ride: Expert Auto Service At Carolina Auto Service

February 27, 2024

January 25, 2024

January 25, 2024

January 24, 2024

January 19, 2024

01 Aug

27 Feb

25 Jan

25 Jan

24 Jan

19 Jan