Triangle

MediumDynamic Programming · Grid DP🧩 Grid DP LeetCode #120 ↗Updated Oct 30, 2026

Problem

You are given a number triangle as a list of rows, where row r holds r + 1 integers. Start at the single top value and walk to the bottom row; from index c you may step to index c or c + 1 of the next row. Return the smallest possible sum of the values along such a walk.

Input[[2],[3,4],[6,5,7],[4,1,8,3]]Output11 (2 + 3 + 5 + 1)

Input[[-10]]Output-10

1 ≤ rows ≤ 200 · -10⁴ ≤ value ≤ 10⁴ · Follow-up: use only O(rows) extra space.

Try it yourself

Java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Work bottom-up: the best walk starting at (r, c) is its value plus the cheaper of the two best walks just below it. The bottom row is its own answer, and the top cell ends up holding the result — one array of length rows suffices.

PatternGrid DP

Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.

Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.

Open the Grid DP guide →

Approaches

Brute ForceTry Every Walk (Recursion)

Time O(2ⁿ)Space O(n)

From each cell, recursively compute the best walk through the left child and the right child and keep the smaller. Every one of the 2^n-1 walks is explored.

Java

public int minimumTotal(List<List<Integer>> triangle) {
    return best(triangle, 0, 0);
}

// Minimum sum of a walk that starts at (r, c) and ends on the last row
private int best(List<List<Integer>> tri, int r, int c) {
    int value = tri.get(r).get(c);
    if (r == tri.size() - 1) return value;
    return value + Math.min(best(tri, r + 1, c), best(tri, r + 1, c + 1));
}

Direct translation of the rules, but inner cells are re-solved many times.

BetterTop-Down Memoization

Time O(n²)Space O(n²)

The answer for a cell depends only on (r, c), and there are only about n²/2 cells. Cache each result the first time it is computed so every cell is solved once.

Java

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    Integer[][] memo = new Integer[n][n];   // null = not computed (values may be negative)
    return best(triangle, 0, 0, memo);
}

private int best(List<List<Integer>> tri, int r, int c, Integer[][] memo) {
    if (memo[r][c] != null) return memo[r][c];
    int value = tri.get(r).get(c);
    int result = (r == tri.size() - 1) ? value
            : value + Math.min(best(tri, r + 1, c, memo), best(tri, r + 1, c + 1, memo));
    memo[r][c] = result;
    return result;
}

Polynomial and keeps the recursive shape, but stores a full triangle of results.

OptimalBottom-Up 1-D DP

Time O(n²)Space O(n)

Copy the last row into dp. Then for each row going upward, overwrite dp[c] = value + min(dp[c], dp[c+1]) from left to right — position c+1 is still the old (lower-row) value when we read it.

Java

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n];
    for (int c = 0; c < n; c++) dp[c] = triangle.get(n - 1).get(c);   // bottom row
    for (int r = n - 2; r >= 0; r--) {
        List<Integer> row = triangle.get(r);
        for (int c = 0; c <= r; c++) {
            dp[c] = row.get(c) + Math.min(dp[c], dp[c + 1]);
        }
    }
    return dp[0];
}

Dry run[[2],[3,4],[6,5,7],[4,1,8,3]]

t answer changed

row 3
4

1

8

3

copy bottom row
row 2
7

6

10

3

6+1, 5+1, 7+3
row 1
9

10

10

3

3+6, 4+6
row 0
11
t
10

10

3

2+9 = 11 ✔

Visits each value once, uses one row of memory and leaves the input untouched.

Pro tip

Going bottom-up removes all boundary checks: the top has one cell, so the answer is simply dp[0] — no final min over a row.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Walk (Recursion)	`O(2ⁿ)`	`O(n)`
Better	Top-Down Memoization	`O(n²)`	`O(n²)`
Optimal	Bottom-Up 1-D DP	`O(n²)`	`O(n)`

Common pitfalls

Greedy “take the smaller child” — a cheap step can lead into an expensive subtree.
Using int[][] memo with 0 as “unset” — 0 (or negatives) are real sums.
Top-down in place needs a final min over the last row; bottom-up does not.

Interview tips

Ask whether you may modify the input — if yes, you can even reuse the last row.
Explain why left-to-right is safe in the 1-D update (dp[c+1] is read before overwritten).
Show a counter-example to greedy before jumping into DP.

Pattern

Path DP on a DAG-shaped grid → each cell's best depends on a few neighbours in the next row, so roll one row of state.

My notes saved in this browser