Triangle

Medium

Fill upward from the base

Problem

Find the minimum path sum from top to bottom of a triangle, moving to adjacent numbers below.

In simple words

Work bottom-up: each cell takes its value plus the smaller of the two cells below it.

The idea

Working bottom-up removes the boundary special cases: each cell becomes its value plus the smaller of the two cells below it, and the apex ends up holding the answer. Top-down would need to track which positions are reachable.

The trick

Bottom-up avoids all edge handling.
The answer ends at dp[0][0].
In-place on the triangle uses O(1) extra space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n^2)spaceO(n)

1dp[j]=tri[i][j]+min(dp[j],dp[j+1]) from bottom row up

Input

array: [2]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output:: 11
Explanation:: 2→3→5→1 sums to the minimum 11.

Example 2

Input:: triangle = [[-10]]
Output:: -10
Explanation:: Single element.

Example 3

Input:: triangle = [[1],[2,3]]
Output:: 3
Explanation:: 1+2 = 3.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.