Triangle
Find the minimum path sum from the top of a triangle to the bottom with bottom-up DP: each cell adds the cheaper of its two children.
Problem Understanding
Triangle: given a triangle array, return the minimum path sum from top to bottom. From index j in one row you may move to index j or j + 1 in the next row.
Example: [[2],[3,4],[6,5,7],[4,1,8,3]] returns 11: 2 + 3 + 5 + 1.
The Intuition: Let the Bottom Decide
The cheapest path from any cell depends only on the cells below it. So work upward:
- The bottom row needs no work: each value is the best path from that cell.
- A cell one row up chooses the cheaper of its two children:
best[i][j] = triangle[i][j] + min(best[i+1][j], best[i+1][j+1]). - Repeat to the top. The top cell holds the answer.
This is the same "value plus the cheaper neighbour" rule as Minimum Path Sum, on a triangle instead of a grid, and the same shape as Pascal's Triangle, with min instead of +. One array of the bottom row's length is all the dynamic programming needs.
Interactive Walkthrough
Under each cell is its best sum to the bottom, filled from the bottom row up. The cell being computed is solid and the cheaper child it used is tinted; the minimum path turns green at the end. Try Greedy trap to see why taking the cheaper step every time fails.
Dry Run Table
Input: [[2],[3,4],[6,5,7],[4,1,8,3]]. dp starts as the bottom row [4, 1, 8, 3].
| Row | Cell | Calculation | dp after |
|---|---|---|---|
| 2 | 6 | 6 + min(4, 1) = 7 | [7, 1, 8, 3] |
| 2 | 5 | 5 + min(1, 8) = 6 | [7, 6, 8, 3] |
| 2 | 7 | 7 + min(8, 3) = 10 | [7, 6, 10, 3] |
| 1 | 3 | 3 + min(7, 6) = 9 | [9, 6, 10, 3] |
| 1 | 4 | 4 + min(6, 10) = 10 | [9, 10, 10, 3] |
| 0 | 2 | 2 + min(9, 10) = 11 | [11, 10, 10, 3] |
Answer: dp[0] = 11.
The Solution Template
One array of the bottom row's length, overwritten from left to right in each row going up.
Triangle Code
1var minimumTotal = function(triangle) {2 const dp = [...triangle[triangle.length - 1]];3 for (let i = triangle.length - 2; i >= 0; i--) {4 for (let j = 0; j <= i; j++) {5 dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);6 }7 }8 return dp[0];9};
Edge Cases & Common Mistakes
- One row: the answer is that single value.
- Greedy steps: picking the cheaper child at each level can lead into expensive rows; compare whole sums.
- Top-down without care: the edge cells of each row have only one parent; bottom-up avoids those special cases.
- 1-D update order: going left to right is safe because
dp[j + 1]is overwritten afterdp[j]reads it. - Negative numbers: fine; the recurrence never assumes values are positive.
Summary
Copy the bottom row into dp, then for each row going up set dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). Return dp[0]. O(n²) time over the n(n+1)/2 cells and O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet