Explore Curriculum Notes Playground

Loading...

Loading Curriculum...

Loading Subject...

Loading Topic...

Loading Lesson...

Data Structures and Algorithms Dynamic Programming

Triangle Minimum Path Sum

Lesson 88/97

Loading Lab...

Dynamic Programming • 2D Grids

Triangle Minimum Path Sum

Given a triangle array, return the minimum path sum from top to bottom. For each step, you may move to an adjacent number on the row below.

TimeO(N²)

SpaceO(N)

Try Interactive Simulator

Overview

Instead of starting at the top and branching down (which creates overlapping subproblems), we start at the bottom and work our way up.

Bottom-Up Approach

If we know the minimum path from the bottom to every node in row `R`, we can easily calculate the minimum path to every node in row `R-1`.

The Recurrence

For an element at `(r, c)`, its two children are at `(r+1, c)` and `(r+1, c+1)`. So, `dp[c] = val + min(dp[c], dp[c+1])`.

1D Space Optimization

Because we only ever need the values from the row immediately below us, we can overwrite a single 1D array of size `N` as we move upward.

▶️ Play to watch the algorithm collapse the triangle from bottom to top, carrying the minimum sums upwards.

Current Step

Initialize DP array with the bottom row of the triangle.

SpeedTimeline

1 / 17

2

3

4

6

5

7

4

1

8

3

1D DP Array (Min Path Sums)

4

1

8

3

Code Tracker

:::

1let n = triangle.length;

2let dp = [...triangle[n - 1]];

3for (let r = n - 2; r >= 0; r--) {

4 for (let c = 0; c <= r; c++) {

5 dp[c] = triangle[r][c] + Math.min(dp[c], dp[c + 1]);

6 }

7}

8return dp[0];