LeetCode 120 · Recursion · DP

Triangle, explained with a picture

The cheapest way down a hill.

Recursion · DP
▶ Watch it step by step

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.