Basic Problemsminimizationgrid

Min Sum in a Triangle

Given a triangular arrangement of numbers, and starting at the top while moving down to one of the two adjacent numbers on the row below at each step, find the smallest possible sum along any path to the bottom row.

Do this lesson first: coin change

Example input

a 9-row triangle, rows top to bottom: 4 / 6 5 / 2 8 5 / 7 2 2 5 / 4 5 2 5 6 / 1 9 7 8 5 1 / 7 3 9 2 6 2 2 / 8 3 3 4 9 3 8 8 / 6 9 4 8 5 1 5 7 5

Expected output

32

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][c] is the smallest total of any descent that starts at the apex, steps down one row at a time onto one of the two numbers immediately below, and finishes ON the number at row r, column c, that number itself included. Two numbers name the state, the row and the column, so the table is a grid even though the input is a triangle. The cell holds a total and nothing about which columns the descent passed through; if you want the path itself you walk the table back up afterwards.

dp[r][c] = tri[r][c] + min(dp[r - 1][c - 1], dp[r - 1][c])

Ask which number the descent was standing on one row up. To arrive at (r, c) it can only have come from the number up and to the left, (r - 1, c - 1), or the number directly above, (r - 1, c), because those are the only two positions whose own two downward steps include this one. Whichever it was, the part of the descent above that point has to be a cheapest descent to that neighbour, which is the same question on a shorter triangle, and tri[r][c] is paid once either way. So take the smaller of the two and add this cell's own number. It is a min rather than a sum because exactly one of the two steps actually happened, the same reason min-cost-path takes a min where count-all-paths-in-a-grid adds. The ragged shape bites at the edges: column 0 has nothing up and to its left, and the last number of a row, column r, has nothing directly above it, so those cells have one candidate instead of two.

dp[0][0] = tri[0][0] = 4: a descent that has only reached row 0 is standing on the apex and has paid for it, so the apex's own number is the whole of the cell. Every other cell of the triangle is computed. THE DOTS ARE NOT ZEROS, and this is the one thing on this page a learner can misread into a different answer. A grid has to be a rectangle, so the table is declared size by size, but only the cells with column <= row belong to the triangle; every position above the diagonal renders as a dot because it DOES NOT EXIST. If those dots were zeros they would be free numbers to stand on, and the cheapest descent would wander out into the empty half of the table and come back with a total far below the truth. Nothing is ever written to a dot and no cell ever depends on one, which is exactly why the edge cells have one genuine candidate rather than one real candidate plus one convenient zero. Filling row-major, left to right within each row, means both of the numbers a cell can descend from are final before it reads them, which is the only ordering property the recurrence needs.

Tabulation, and it is the same row-major sweep as min-cost-path and count-all-paths-in-a-grid with a different table shape and a different operator at the cell. Two things about this page deserve saying out loud. First, the DIRECTION. This table accumulates DOWNWARD: a cell holds the cheapest descent from the apex that ends on it, and the answer is scanned out of the bottom row at the end. Most published solutions run the other way, folding each row into the row above it until the apex alone holds the answer, which needs no final scan at all. Both are the same problem read from opposite ends and both return the same number; the downward form is the one a strictly top-to-bottom, left-to-right sweep can express, which is why the table in front of you fills this way rather than the way you have probably seen it written. Second, the cost. The triangle holds size times size plus one, over two, cells, so the time is O(n^2) in the number of rows, and since a cell only ever reads the row above it, one rolling row of length n is enough space. Memoization would visit the same cells with call overhead on top, because every cell of the triangle lies on some descent.

Time O(n^2) for n rowsSpace O(n^2), reducible to O(n) with one rolling row

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0][0] = tri[0][0] = 4: a descent that has only reached row 0 is standing on the apex and has paid for it, so the apex's own number is the whole of the cell. Every other cell of the triangle is computed. THE DOTS ARE NOT ZEROS, and this is the one thing on this page a learner can misread into a different answer. A grid has to be a rectangle, so the table is declared size by size, but only the cells with column <= row belong to the triangle; every position above the diagonal renders as a dot because it DOES NOT EXIST. If those dots were zeros they would be free numbers to stand on, and the cheapest descent would wander out into the empty half of the table and come back with a total far below the truth. Nothing is ever written to a dot and no cell ever depends on one, which is exactly why the edge cells have one genuine candidate rather than one real candidate plus one convenient zero. Filling row-major, left to right within each row, means both of the numbers a cell can descend from are final before it reads them, which is the only ordering property the recurrence needs.

row r

0

1

2

3

4

5

6

7

8

0

4

·

1

10

9

·

2

12

17

14

·

3

19

14

16

19

·

4

23

19

16

21

25

·

5

24

28

23

24

26

·

6

31

27

32

25

30

28

·

7

39

30

29

34

31

36

·

8

45

39

34

37

34

32

36

43

41

column c: cheapest descent from the apex ending on (r, c)

min-sum-in-a-triangle.ts

1function minTriangleSum(tri) {
2 const n = tri.length;
3 const dp = tri.map((row) => new Array(row.length).fill(0));
4 dp[0][0] = tri[0][0];
5 for (let r = 1; r < n; r++) {
6 for (let c = 0; c <= r; c++) {
7 const upLeft = c > 0 ? dp[r - 1][c - 1] : Infinity;
8 const above = c < r ? dp[r - 1][c] : Infinity;
9 dp[r][c] = tri[r][c] + Math.min(upLeft, above);
10 }
11 }
12 return Math.min(...dp[n - 1]);
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

min-sum-in-a-triangle.ts

1function minTriangleSum(tri) {
2 const n = tri.length;
3 const dp = tri.map((row) => new Array(row.length).fill(0));
4 dp[0][0] = tri[0][0];
5 for (let r = 1; r < n; r++) {
6 for (let c = 0; c <= r; c++) {
7 const upLeft = c > 0 ? dp[r - 1][c - 1] : Infinity;
8 const above = c < r ? dp[r - 1][c] : Infinity;
9 dp[r][c] = tri[r][c] + Math.min(upLeft, above);
10 }
11 }
12 return Math.min(...dp[n - 1]);
13}

Where people go wrong

Stepping onto the smaller of the two numbers below at every move. Greedy descent is the natural first instinct and it is wrong at every size from 3 rows up: on 3 rows it takes 4, 5, 5 for 14 while the true minimum is 4, 6, 2 for 12, and on the full 9 rows it pays 36 where the table pays 32. A small number is worth nothing if it is fenced in by large ones below it, which is precisely what a one-step-ahead rule cannot see. The second trap is reading the last cell of the bottom row as the answer; only the SMALLEST cell of the bottom row is, and here that is column 5 while the last cell holds 41. The third is treating the dots above the diagonal as zeros. They are positions that do not exist, and a zero there is a free number the descent would gladly cheat its way through.

Maximize the total along the descent instead of minimizing it.
Swap min for max, then scan the bottom row for its largest cell instead of its smallest. Nothing else moves, exactly as the one word between min-cost-path and its own maximizing variation.
Accumulate upward from the bottom row instead of downward from the apex.
dp[r][c] = tri[r][c] + min(dp[r + 1][c], dp[r + 1][c + 1]), and the answer becomes the single cell dp[0][0], so the scan across the bottom row disappears and with it any need to remember where the best cell was. It is this same problem read from the other end and it returns the same number; it just cannot be shown as a top-to-bottom sweep, which is why this page runs downward.
Allow a step onto any number of the next row, not only the two adjacent ones.
Every cell of the row above becomes a candidate, so the min widens from two terms to r terms. The consequence is worth noticing: the choices at each row stop interacting at all, so the answer collapses to the sum of each row's smallest number and no table is needed. Adjacency is the only thing making this a dynamic programming problem.

Ways to Triangulate a Polygon Minimum Perfect Squares