The problem
Given a triangle of numbers, find the smallest total on a path from top to bottom, moving to an adjacent number on the row below each step.
Input: 2 / 3,4 / 6,5,7 / 4,1,8,3 Output: 11 (2 + 3 + 5 + 1)
Picture it
Picture a hiker going down a hill of rest stops, each charging a toll. Working from the bottom row up, each stop’s best cost is its toll plus the cheaper of the two stops below it. The top ends up holding the answer.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Bottom-up DP on one row. O(n²) time, O(n) memory.
Python solution
def minimum_total(tri):
best = tri[-1][:] # cost from the bottom row
for r in range(len(tri) - 2, -1, -1):
for c in range(r + 1):
best[c] = tri[r][c] + min(best[c], best[c + 1])
return best[0]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.