Triangle: Bottom-Up DP for Minimum Path Sum

Given a triangle array, find the minimum path sum from top to bottom. At each step you can move to an adjacent number on the row below, meaning from index i you can move to index i or i + 1 in the next row.

This is LeetCode 120: Triangle, and it is one of the cleanest examples of bottom-up DP you will encounter. Unlike grid problems where you move right and down on a rectangle, this problem has a triangular structure where each row grows by one element. That shape makes bottom-up processing especially natural, because the last row needs no computation at all.

Why this problem matters

Triangle teaches you to think about DP direction. Most grid DP problems fill from top-left to bottom-right, but Triangle is easier to solve from the bottom up. Starting at the last row and folding upward eliminates the need for special boundary handling and lets you reduce the entire triangle into a single value. The follow-up asks for O(n) space, and the bottom-up approach delivers that naturally by reusing a single array.

If you have solved Minimum Path Sum, you already know how to pick the cheaper of two neighbors. Triangle uses the same idea, but the neighbors are below instead of above and to the left, and the structure is triangular instead of rectangular.

The approach: bottom-up DP

Instead of starting at the top and branching downward (which leads to exponential recursion), start at the bottom row and work up.

The idea:

1. Copy the bottom row into a dp array.
2. For each row above the bottom (going upward), update dp[j] to be the current cell's value plus the minimum of dp[j] and dp[j + 1].
3. After processing all rows, dp[0] holds the answer.

Why does this work? At each cell, you are choosing the cheaper of the two paths below it and adding the current cell's cost. By the time you reach the top, dp[0] contains the minimum cost from the top to any reachable cell at the bottom.

Let's trace through the triangle [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]:

The minimum path sum is 11, following the path 2, 3, 5, 1.

Python solution

def minimum_total(triangle):
    dp = triangle[-1][:]

    for row in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[row])):
            dp[j] = triangle[row][j] + min(dp[j], dp[j + 1])

    return dp[0]

Walkthrough

Start by copying the last row [4, 1, 8, 3] into dp. This is the base case: the cost to reach any cell in the bottom row is just the cell's value.

Now process row 2 (values [6, 5, 7]). For j = 0, the value is 6 + min(dp[0], dp[1]) = 6 + min(4, 1) = 7. For j = 1, the value is 5 + min(dp[1], dp[2]) = 5 + min(1, 8) = 6. For j = 2, the value is 7 + min(dp[2], dp[3]) = 7 + min(8, 3) = 10. After this row, dp = [7, 6, 10, 3]. The last element is stale but never read again.

Process row 1 (values [3, 4]). For j = 0: 3 + min(7, 6) = 9. For j = 1: 4 + min(6, 10) = 10. After this row, dp = [9, 10, 10, 3].

Process row 0 (value [2]). For j = 0: 2 + min(9, 10) = 11. The answer is dp[0] = 11.

Complexity analysis

Time: O(n^2) where n is the number of rows. The triangle has 1 + 2 + ... + n = n(n+1)/2 cells, each visited once.

Space: O(n) for the dp array, which has the same length as the bottom row.

The bottom-up approach hits the optimal O(n) space directly, which is exactly what the follow-up asks for. There is no need for a separate space optimization step because the bottom-up direction naturally overwrites values that are no longer needed.

The building blocks

This problem is built on two reusable patterns:

Bottom-up triangle DP. Instead of filling a grid from top-left to bottom-right, you start at the base of a triangular structure and fold upward. Each cell combines its own value with the minimum (or maximum) of two adjacent children. The triangular shape means row r has r + 1 elements, and the adjacency rule (index i connects to index i and i + 1 below) is what defines the subproblem structure. This same pattern appears in burst balloons and other triangle-shaped DP problems.

In-place row reduction. The dp array starts as a copy of the bottom row and gets shorter (in terms of meaningful values) with each iteration. You overwrite dp[j] with the new value for the row above, and the tail of the array becomes stale. This avoids allocating a new array for each row and keeps space at O(n). The technique works whenever your DP processes rows from bottom to top and each row is shorter than the one below.

These two building blocks combine to give you a clean, space-efficient solution with no boundary cases to worry about. The bottom-up direction eliminates the first-row and first-column edge cases that make top-down grid DP verbose.

Edge cases to watch for

• Single element: triangle = [[5]]. The answer is 5. The loop body never executes because there is only one row.
• Two rows: triangle = [[1], [2, 3]]. Process row 0: 1 + min(2, 3) = 3. Make sure your loop range handles len(triangle) - 2 = 0 correctly (it does, since range(0, -1, -1) yields [0]).
• All same values: triangle = [[1], [1, 1], [1, 1, 1]]. Every path has the same sum (3). The algorithm handles this without any special logic.
• Large triangle: with n = 200 rows, the bottom row has 200 elements and the total cell count is 20,100. O(n^2) time handles this instantly.

From understanding to recall

You have traced through the bottom-up DP, seen why the direction matters, and understand how stale values stay out of the way. But reading through a walkthrough and producing the solution under pressure are different skills.

The key insight to internalize is the direction. When you see a triangle where each cell connects to two cells below, your first instinct should be to start from the bottom. That eliminates boundary handling and gives you O(n) space without any extra work.

Spaced repetition locks this in. You revisit the problem at increasing intervals, each time writing the bottom-up loop from scratch, remembering to copy the last row, iterate upward, and take the minimum of two children. After a few reps, the pattern is automatic.

The bottom-up triangle DP pattern and in-place row reduction are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Minimum Path Sum - The rectangular grid version of this idea, where you pick the cheaper of two neighbors (above and left) instead of two children below
• Climbing Stairs - Your first DP problem, teaching the recursion-to-table pipeline that Triangle builds on