How do you approach Triangle?

Work bottom-up: start from the last row and fold each row into the one above.

What are common mistakes on Triangle?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Triangle

MediumAlgorithms

Description

Given a `triangle` array, return the minimum path sum from top to bottom. At each step you may move to an adjacent number on the row below: from index `i` you may go to index `i` or `i + 1`.

Example 1

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

Output: 11

Explanation: 2 + 3 + 5 + 1 = 11.

Constraints

- 1 <= triangle.length <= 200 - triangle[i].length == i + 1 - -10^4 <= triangle[i][j] <= 10^4

Triangle: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 3 test cases (1 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 2-step hint ladder

Work bottom-up: start from the last row and fold each row into the one above.
dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).

The optimal approach

Show the approach: The approach

Bottom-up DP. Initialize `dp` with the last row. For each row above, set `dp[j] = triangle[i][j] + min(dp[j], dp[j+1])`. After folding all rows, `dp[0]` is the minimum top-to-bottom path sum.

Time: O(n²). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.