Minimize a Triangle Path with Adjacent Downward Steps
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given rows of a numeric triangle, return the smallest sum along a path from its top entry to its bottom row. From index `i` in one row, the next step may go only to index `i` or index `i+1` in the following row. Include one value from each row.
```cpp
int minimumTotal(vector<vector<int>>& triangle);
```
### Examples
```text
Input: triangle = [[3],[2,5],[-4,1,-2],[6,-3,4,2]]
Output: -2
```
A minimum path is 3→2→-4→-3.
```text
Input: triangle = [[7]]
Output: 7
```
### Constraints
- The number of rows is between 1 and 200.
- The first row has length 1, and each later row has one more entry than its predecessor.
- Every entry lies between -10000 and 10000, inclusive.
### Optional follow-up
Use only `O(n)` extra space, where `n` is the number of rows.
Overview: Find a triangle’s minimum adjacent-step path sum with bottom-up suffix costs and one row of extra memory.