# LeetCode 120: Triangle

## Problem Restatement

We are given a triangle array.

Each row has one more element than the previous row.

Starting from the top, we may move only to one of the two adjacent numbers directly below:

- Same index
- Next index

We must find the minimum path sum from top to bottom.

The official problem defines adjacency exactly this way. ([leetcode.com](https://leetcode.com/problems/triangle/?utm_source=chatgpt.com))

For example:

```python
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
```

One valid path is:

```text
2 -> 3 -> 5 -> 1
```

Its sum is:

```python
11
```

This is the minimum possible sum, so the answer is:

```python
11
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A triangle array |
| Output | Minimum path sum from top to bottom |
| Allowed moves | Down or down-right |
| Goal | Minimize total sum |

The function shape is:

```python
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        ...
```

## Examples

Consider:

```python
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
```

Possible paths include:

```text
2 -> 3 -> 6 -> 4 = 15
2 -> 3 -> 5 -> 1 = 11
2 -> 4 -> 5 -> 1 = 12
2 -> 4 -> 7 -> 3 = 16
```

The minimum is:

```python
11
```

Now consider:

```python
triangle = [
    [-10]
]
```

The answer is:

```python
-10
```

because there is only one possible path.

## First Thought: Try Every Path

At each row, we have two choices:

1. Move downward.
2. Move down-right.

That creates a binary decision tree.

For a triangle with many rows, the number of paths grows exponentially.

We need dynamic programming because many subproblems repeat.

## Key Insight

Suppose we are at:

```python
triangle[i][j]
```

The best path from this position depends only on:

1. The best path below it.
2. The best path down-right from it.

So:

$$
dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
$$

This suggests a bottom-up approach.

Start from the last row, which already contains complete path sums.

Then move upward row by row.

## Bottom-Up Dynamic Programming

Suppose the bottom row is:

```python
[4, 1, 8, 3]
```

These values are already final path sums because no rows exist below them.

Now process the row above:

```python
[6, 5, 7]
```

For `6`:

```python
6 + min(4, 1) = 7
```

For `5`:

```python
5 + min(1, 8) = 6
```

For `7`:

```python
7 + min(8, 3) = 10
```

Now the row becomes:

```python
[7, 6, 10]
```

Repeat upward until reaching the top.

The top value becomes the minimum path sum.

## Algorithm

Create a copy of the last row:

```python
dp = triangle[-1][:]
```

Then process rows upward:

For each row `i` from bottom-1 to top:

For each column `j`:

$$
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
$$

At the end:

```python
dp[0]
```

contains the minimum total.

## Correctness

The algorithm processes the triangle from bottom to top.

Initially, `dp[j]` stores the minimum path sum starting from the bottom-row element:

```python
triangle[last_row][j]
```

This is correct because no further moves are possible.

Now consider a higher position:

```python
triangle[i][j]
```

From this position, the next move can go only to:

```python
triangle[i+1][j]
triangle[i+1][j+1]
```

By the induction hypothesis, `dp[j]` and `dp[j+1]` already store the minimum path sums starting from those two positions.

Therefore, the minimum path sum starting at:

```python
triangle[i][j]
```

is:

$$
triangle[i][j] + min(dp[j], dp[j+1])
$$

Updating `dp[j]` with this value is correct.

After processing all rows upward, `dp[0]` stores the minimum path sum from the top of the triangle to the bottom.

Thus, the algorithm correctly computes the minimum total.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Every triangle value is processed once |
| Space | `O(n)` | Only one DP row is stored |

Here, `n` is the number of rows.

The triangle contains approximately:

$$
n(n+1)/2
$$

values total.

## Implementation

```python
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        dp = triangle[-1][:]

        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

        return dp[0]
```

## Code Explanation

Copy the last row:

```python
dp = triangle[-1][:]
```

These are the initial minimum path sums.

Process rows upward:

```python
for i in range(len(triangle) - 2, -1, -1):
```

Process every value in the row:

```python
for j in range(len(triangle[i])):
```

Update the minimum path sum:

```python
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
```

`dp[j]` and `dp[j+1]` represent the two reachable positions below.

Finally:

```python
return dp[0]
```

The top value becomes the answer.

## Testing

```python
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        dp = triangle[-1][:]

        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

        return dp[0]

def run_tests():
    s = Solution()

    assert s.minimumTotal([
        [2],
        [3, 4],
        [6, 5, 7],
        [4, 1, 8, 3]
    ]) == 11

    assert s.minimumTotal([
        [-10]
    ]) == -10

    assert s.minimumTotal([
        [1],
        [2, 3]
    ]) == 3

    assert s.minimumTotal([
        [5],
        [9, 6],
        [4, 6, 8],
        [0, 7, 1, 5]
    ]) == 18

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Confirms DP recurrence |
| Single row | Minimum triangle |
| Two rows | Small transition case |
| Larger triangle | Confirms repeated bottom-up updates |