A grid that isn't rectangular
The same "cheapest way in" idea, moving down a shape whose rows grow by one each time. About 12 minutes.
Walking down a pyramid of numbers
Picture a pyramid of numbers, one at the top and one more in each row below. You start at the top, and from each number you step down to one of the two numbers just below it. Add up everything you step on. What's the smallest total you can reach the bottom with?
The shape is new but the idea isn't. From any number there are exactly two ways to continue, and you want the cheaper one.
Start from the bottom and climb up
Going top-down, the last row has many possible finishing points. Going bottom-up is simpler: a number on the bottom row costs just itself, because there's nowhere left to go.
Then move up one row. Each number costs itself plus the cheaper of the two numbers below it, and you can overwrite one row of answers as you climb. When you reach the top, its single number holds the answer: 11 in the example.
best = triangle[-1][:] # start from the bottom row
The bottom row has nowhere further to go, so its cost is just its own value.
The row below costs 7, 6 and 10 (left to right). A number 4 sits above the 6 and the 10. What does that 4 cost?
- A10
- B11
- C4
Show the answer
10. From the 4 you can step to the 6 or the 10. The 6 is cheaper: 4 + 6 = 10.
Minimum path sum in a triangle
triangle is a list of rows, where row i has i + 1 numbers. Starting at the single number in row 0 and moving to either of the two numbers directly below it each step (row i, position j moves to row i + 1, position j or j + 1), return the smallest possible sum from the top to the bottom row.
triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] → 11
1 ≤ rows ≤ 200 · −10,000 ≤ each value ≤ 10,000