Why it works
- From a cell, the cheapest way down is its own number plus the cheaper of the cheapest ways down from the two cells under it. Going row by row from the bottom, those two are always ready.
- Every cell of the bottom row is a finished walk on its own, so the copy of the triangle already holds the right values there, and nothing else needs a base case.
- Choosing the cheaper cell on the way down looks only one row ahead: here it takes the 1 and pays 17. Each cell of best has already seen every walk below it.
Complexity
Time O(n²) for n rows: each of the about n²/2 cells is one min and one addition. Memory O(n²) for the copy; a row reads only the row under it, so one array of n numbers is enough.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗