Problem 29.4 · DP on GridsMedium

Triangle

What it teaches: Bottom-up from the last row makes the answer land in one cell, with O(n) memory.

Practise it on judges as “Triangle”.

The problem

From the top of a triangle, move to an adjacent number on the row below (index i or i + 1). Return the minimum path sum to the bottom.

Example 1

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11

2 + 3 + 5 + 1.

Constraints

1 ≤ rows ≤ 200

Pattern clues in the wording

→ Minimum path through rows with two choices

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]	11
2	triangle = [[-10]]	-10

From slow to fast

Approaches

1. Bottom-up one row · O(n²)

Bottom-up one row

Time O(n²) Space O(n)

best = copy of the last row; for rows from second-last up, best[i] = row[i] + min(best[i], best[i + 1]). Answer best[0].

Approach 1

import java.util.*;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] best = new int[n + 1];
        for (int r = n - 1; r >= 0; r--)
            for (int i = 0; i <= r; i++)
                best[i] = triangle.get(r).get(i) + Math.min(best[i], best[i + 1]);
        return best[0];
    }
}

Verdict: No edge cases at the triangle's sides.

Before you submit

Edge cases and common mistakes

Test these inputs

One row
Negative values

Mistakes people make

Greedy choosing the smaller child at each step.

Interview

Follow-up questions

Why is bottom-up simpler than top-down here?

Command Palette

The problem

Approaches

Bottom-up one row

Edge cases and common mistakes

Follow-up questions