Medium Problemsoptimizationlinear

Box-Stacking Problem

Given n boxes, each with a length, width, and height, and free rotation of each box among its three orientations, stack boxes so that each box's base fits strictly inside the base of the box beneath it. Maximize the total height of the stack.

Do this lesson first: house robber

Example input

boxes = [[4, 6, 7], [1, 2, 3], [4, 5, 6], [5, 8, 9], [2, 4, 10]], every box free to rotate

Expected output

29

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[i] = height[i] + max over every earlier rotation j whose base strictly contains rotation i's base in both dimensions, from a different box, of dp[j], or height[i] alone if no such j exists

Ask what sat directly beneath this rotation in the tallest stack that finishes with it on top. It has to be an earlier rotation, sorted before it because its base area is at least as large, whose base strictly contains this rotation's base in both dimensions, and which comes from a different original box, since a box cannot rest on a different orientation of itself. Whichever qualifying rotation already carries the tallest stack beneath it is the one to build on, compared rather than summed, since only one rotation actually sits directly beneath this one.

dp[0] = 5 is the only declared base: sorted by decreasing base area, the very first rotation has the largest base of any in the table, so no earlier, bigger base exists for it to rest on, and a stack of just this rotation alone stands as tall as its own height. That base, 9 by 8, only exists by rotating the fourth box onto its length as the new height, not the orientation it was given, and the cell does get read often afterward, by every later rotation whose base fits strictly inside 9 by 8 from a different box. Some compute cells still resolve with no read at all, the same zero-dependency shape as the other three problems in this batch: dp[3] is exactly that case, since the only rotation whose base numerically contains 8 by 5 is dp[0], and dp[0] comes from the same original box, so the box-identity check rules it out and dp[3] is left standing alone on its own height. That specific cell then turns out to anchor the entire optimal stack once later rotations from other boxes are free to build on it. Every other cell depends only on smaller indices, so filling left to right guarantees every candidate that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up tallest, not necessarily the last one, the table also has to track that argmax as it fills.

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] = 5 is the only declared base: sorted by decreasing base area, the very first rotation has the largest base of any in the table, so no earlier, bigger base exists for it to rest on, and a stack of just this rotation alone stands as tall as its own height. That base, 9 by 8, only exists by rotating the fourth box onto its length as the new height, not the orientation it was given, and the cell does get read often afterward, by every later rotation whose base fits strictly inside 9 by 8 from a different box. Some compute cells still resolve with no read at all, the same zero-dependency shape as the other three problems in this batch: dp[3] is exactly that case, since the only rotation whose base numerically contains 8 by 5 is dp[0], and dp[0] comes from the same original box, so the box-identity check rules it out and dp[3] is left standing alone on its own height. That specific cell then turns out to anchor the entire optimal stack once later rotations from other boxes are free to build on it. Every other cell depends only on smaller indices, so filling left to right guarantees every candidate that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up tallest, not necessarily the last one, the table also has to track that argmax as it fills.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

i=11

i=12

i=13

i=14

5

8

9

2

13

15

16

14

15

4

26

17

28

29

box-stacking.ts

1function boxStacking(boxes) {
2 const rotations = [];
3 boxes.forEach(([l, w, h], boxIndex) => {
4 for (const [d1, d2, height] of [[l, w, h], [l, h, w], [w, h, l]]) {
5 rotations.push({ base1: Math.max(d1, d2), base2: Math.min(d1, d2), height, boxIndex });
6 }
7 });
8 rotations.sort((a, b) => b.base1 * b.base2 - a.base1 * a.base2);
9 const dp = rotations.map((r) => r.height);
10 let best = dp[0];
11 for (let i = 1; i < rotations.length; i++) {
12 for (let j = 0; j < i; j++) {
13 const a = rotations[j], b = rotations[i];
14 if (a.base1 > b.base1 && a.base2 > b.base2 && a.boxIndex !== b.boxIndex) {
15 dp[i] = Math.max(dp[i], dp[j] + b.height);
16 }
17 }
18 best = Math.max(best, dp[i]);
19 }
20 return best;
21}

Base caseComputedBeing readAnswer

The code, the trap, the variations

box-stacking.ts

1function boxStacking(boxes) {
2 const rotations = [];
3 boxes.forEach(([l, w, h], boxIndex) => {
4 for (const [d1, d2, height] of [[l, w, h], [l, h, w], [w, h, l]]) {
5 rotations.push({ base1: Math.max(d1, d2), base2: Math.min(d1, d2), height, boxIndex });
6 }
7 });
8 rotations.sort((a, b) => b.base1 * b.base2 - a.base1 * a.base2);
9 const dp = rotations.map((r) => r.height);
10 let best = dp[0];
11 for (let i = 1; i < rotations.length; i++) {
12 for (let j = 0; j < i; j++) {
13 const a = rotations[j], b = rotations[i];
14 if (a.base1 > b.base1 && a.base2 > b.base2 && a.boxIndex !== b.boxIndex) {
15 dp[i] = Math.max(dp[i], dp[j] + b.height);
16 }
17 }
18 best = Math.max(best, dp[i]);
19 }
20 return best;
21}

Where people go wrong

Only considering each box in the orientation it was given, instead of every box's three rotations. The largest base anywhere in this table, 9 by 8, belongs to a rotation of the fourth box that is not its given order: it comes from using that box's length as the new height, a genuine rotation away from [5, 8, 9]. Restricting every box to its given order would shrink the candidate pool before the recurrence even runs and could shrink the answer along with it. The other half of the same trap runs the opposite way: once a box is expanded, its rotations are still the same box, so no rotation may rest on another rotation of itself even when the bases fit. dp[3] is the visible proof, sitting alone with no read despite an 8 by 5 base that fits neatly inside the 9 by 8 above it.

Return one such stack itself, the ordered list of rotations, not just its total height.
Each cell would need to remember which earlier rotation it built on, so the stack can be walked backward from the best cell once found; the height recurrence, the rotation expansion, and the left-to-right order do not change at all.
Require the base to fit inside with at least some margin on every side, instead of merely being strictly smaller.
Only the single comparison changes, from a strict less-than on both base dimensions to a less-than-minus-margin on both; the box-identity check, the plus-height, and the argmax-over-the-table answer all stay exactly the same.

Tile Stacking Problem Partition Problem