Hard Problemsminimizationpartitiongrid

The painter's partition problem

Given n boards of different lengths and k painters who all paint at the same speed, where each painter must paint one contiguous, unsplit block of boards, assign the boards, in order, to minimize the time the slowest painter spends.

Note. This problem is more commonly solved with binary search on the answer; the DP formulation shown here is the derivable, table-based alternative.

Do this lesson first: coin change

Example input

boards = [10, 10, 5, 4, 2, 3, 2, 9, 10, 6], k = 3 painters

Expected output

25

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[p - 1][i - 1] is the least time the SLOWEST of p painters can be held to when the first i boards, in the order they are given, are shared out among them and every painter takes one contiguous, unsplit block. Two numbers name the state, how many painters and how many boards, so the table is a grid rather than a row. The cell holds one time and nothing about where the cuts fell; if you want the blocks themselves you walk the table backwards afterwards. Row index is p - 1 and column index is i - 1, so the bottom right cell is the whole crew on the whole job, and every cell above or to the left of it is a smaller crew, a shorter job, or both. Watch the indices, because this page uses more than one convention. The recurrence below is written the way it reads best, dp[p][i] for p painters over the first i boards, so each of its indices sits one place later than the grid coordinate it points at: the dp[3][10] of the recurrence is the cell the grid labels dp[2][9]. Read every dp[...] here against the words next to it. The recurrence and the derivation under it count painters and boards from 1; every reference to a cell of the grid itself, in this panel and in the step-by-step narration and the gates, uses the zero-based row and column. The code further down is a THIRD labelling, on purpose, because it is written the way you would actually type it: painters zero-based like the grid, boards one-based over a padding column like neither. Its dp[k - 1][n], the grid's dp[2][9] and the recurrence's dp[3][10] are all the same cell, and its dp[p][i] is p + 1 painters where the recurrence's dp[p][i] is p, which is worth holding onto because the highlighted line of code and the narrated cell move together.

dp[p][i] = min over j of max(dp[p - 1][j], load(j + 1, i)), for p painters over the first i boards

Ask where the LAST painter's block BEGINS. If it begins after board j, that painter's time is the load of boards j + 1 through i, a number you add up from the board lengths and from nothing else. The other p - 1 painters then have to cover the first j boards as evenly as they can, which is the same question on a shorter row and a smaller crew, so dp[p - 1][j] already answers it. A crew waits for its slowest member, so this cut costs the crew the LARGER of those two numbers. Every j from p - 1 up to i - 1 is a legal place for that block to begin, exactly one of them is what the best assignment did, and you want the j that makes the larger of the two numbers as small as it can be. Hence a min over maxes. Notice what the max is doing, because it is the part that reads oddly at first: it is not comparing two ways of arriving here, the way min-cost-path compares a step down against a step right. It scores ONE cut by its own worst block. The min is what compares the cuts.

Row 0 is one painter, and one painter has no decision to make: p = 1 means every board from 1 to i is theirs, so dp[0][i - 1] is the plain total of the first i boards. That is why the whole of row 0 is a base rather than a computed cell, and why it reads as a running total, 10, 20, 25, 29 and on up to 61 at ten boards. It is also the only row that needs no comparison, which makes it the right place for a sweep to start. THE DOTS ARE NOT ZEROS, and it is worth being exact about what that does and does not buy you here. A grid has to be a rectangle, so the table is declared 3 rows by however many boards, but a cell with i < p asks three painters to share two boards while every painter must paint at least one contiguous block. That has no answer rather than a cheap one, so those positions render as a dot because they DO NOT EXIST. Nothing is written to them and no cell depends on one: the split range, j from p - 1 up to i - 1, is exactly the range that stays clear of them. Now the part that is easy to get wrong in the other direction, and this page is the exception rather than the rule. On a min-over-SUM table, a zero sitting where a dot belongs is a free move and the min takes it every time: min-sum-in-a-triangle says exactly that about its own dots, and it is right to, because a descent that could stand on the empty half of that table would come back under the truth. It does not transfer here. There is exactly one place the mistake could even bite, since row 0 has no dots at all: widen the range and row 2's leftmost candidate becomes the dot at dp[1][0], which the shipped range never reads. So fill every dot with a zero AND widen the split range to allow every j, and all seven answers come out unchanged, 10, 11, 14, 15, 19, 20 and 25, with not one live cell moving either. The max is what protects this table: a zero prior gets paired with the LARGEST remaining block, so max(0, that block) is just the block. At dp[1][0] that block is boards 2 through 10, a SUFFIX and not one of row 0's prefix totals, and it comes to 51 against a true 25 at ten boards, so the min never takes it. So the min over maxes makes the ragged half harmless, which is a property worth noticing rather than a hazard to fear, and the reason to keep the dots is that a position which does not exist is not a value, not that a zero would hand you the wrong number. The fill order needs one property and has it. Every candidate a cell reads lies in the row ABOVE and at a column strictly to the LEFT of this one, never in this row and never further right, so a row-major sweep left to right within each row has all of them final before the cell asks for them.

Tabulation: a row-major sweep over k times n cells with a scan over the split points inside each one, so O(k n^2) time for k painters and n boards, and O(k n) space that collapses to one rolling row of length n because a cell only ever reads the row above. Memoization deserves a measurement here rather than the usual sentence, because on this table the usual sentence is false. Work backwards from the answer and most of the table turns out not to be needed: 5 of 9 live cells at four boards, then 7 of 12, 9 of 15, 11 of 18, 13 of 21, 15 of 24, and 17 of 27 at ten, which is 2n - 3 of 3n - 3 at every slider position. The reason is that no cell reads the bottom row at all, so row 2 contributes exactly one needed cell, the answer itself, out of the n - 2 the sweep fills, and every other cell of that row you watch appear is a cell a memoized solve never computes. Memoization here therefore does strictly LESS work, not the same work with call overhead bolted on. Two reasons to prefer the sweep survive that measurement: no call overhead per cell, and the rolling row, which a cache cannot have because it has to persist. Now the honest part, because this problem's own note says binary search on the answer is the more common solution and the note is right. Binary search runs in O(n log T) where T is the total length of all the boards, 61 at ten boards here: guess a time limit, walk the boards once opening a new painter whenever the current block would exceed the guess, and check whether the painters you have suffice. Reach for that one. It is what an interviewer expects and what you would ship. It also asks you for two things the table does not. You have to SUPPLY a candidate answer to test rather than derive one, so you need bounds to search between, and you have to see that feasibility is MONOTONE in the guess, that a limit which works keeps working when raised, before the search is even valid. Neither is hard, but both are insight rather than mechanism, and without the monotonicity the binary search is a leap of faith. The table asks for no such insight: it derives the number from the structure of the problem, it generalises to any k by adding rows, and it hands you the cuts if you walk it back. That is why it is worth seeing even though it is not what you would reach for. It is the derivation; the binary search is the shortcut you take once you believe the answer is there to be found. And the asymptotic gap is not visible at this page's own size: ten boards cost the table 81 scored cut candidates, while a binary search between 10 and 61 walks the ten boards about six times for 60 board visits. They are neck and neck here, and only n growing separates them.

Time O(k × n^2) for k painters and n boards, so 3 × n^2 hereSpace O(k × n), 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.

Row 0 is one painter, and one painter has no decision to make: p = 1 means every board from 1 to i is theirs, so dp[0][i - 1] is the plain total of the first i boards. That is why the whole of row 0 is a base rather than a computed cell, and why it reads as a running total, 10, 20, 25, 29 and on up to 61 at ten boards. It is also the only row that needs no comparison, which makes it the right place for a sweep to start. THE DOTS ARE NOT ZEROS, and it is worth being exact about what that does and does not buy you here. A grid has to be a rectangle, so the table is declared 3 rows by however many boards, but a cell with i < p asks three painters to share two boards while every painter must paint at least one contiguous block. That has no answer rather than a cheap one, so those positions render as a dot because they DO NOT EXIST. Nothing is written to them and no cell depends on one: the split range, j from p - 1 up to i - 1, is exactly the range that stays clear of them. Now the part that is easy to get wrong in the other direction, and this page is the exception rather than the rule. On a min-over-SUM table, a zero sitting where a dot belongs is a free move and the min takes it every time: min-sum-in-a-triangle says exactly that about its own dots, and it is right to, because a descent that could stand on the empty half of that table would come back under the truth. It does not transfer here. There is exactly one place the mistake could even bite, since row 0 has no dots at all: widen the range and row 2's leftmost candidate becomes the dot at dp[1][0], which the shipped range never reads. So fill every dot with a zero AND widen the split range to allow every j, and all seven answers come out unchanged, 10, 11, 14, 15, 19, 20 and 25, with not one live cell moving either. The max is what protects this table: a zero prior gets paired with the LARGEST remaining block, so max(0, that block) is just the block. At dp[1][0] that block is boards 2 through 10, a SUFFIX and not one of row 0's prefix totals, and it comes to 51 against a true 25 at ten boards, so the min never takes it. So the min over maxes makes the ragged half harmless, which is a property worth noticing rather than a hazard to fear, and the reason to keep the dots is that a position which does not exist is not a value, not that a zero would hand you the wrong number. The fill order needs one property and has it. Every candidate a cell reads lies in the row ABOVE and at a column strictly to the LEFT of this one, never in this row and never further right, so a row-major sweep left to right within each row has all of them final before the cell asks for them.

row p - 1: how many painters share the job, so the bottom row is the whole crew

0

1

2

3

4

5

6

7

8

9

0

10

20

25

29

31

34

36

45

55

61

1

·

10

15

19

20

25

29

31

2

·

10

11

14

15

19

20

25

column i - 1: how many boards are in the job, so the cell is the slowest painter's time over the first i boards

painters-partition.ts

1function painterPartition(boards, k) {
2 const n = boards.length;
3 const pre = [0];
4 for (const b of boards) pre.push(pre[pre.length - 1] + b);
5 const dp = Array.from({ length: k }, () => new Array(n + 1).fill(Infinity));
6 for (let i = 1; i <= n; i++) dp[0][i] = pre[i];
7 for (let p = 1; p < k; p++) {
8 for (let i = p + 1; i <= n; i++) {
9 for (let j = p; j < i; j++) {
10 const slowest = Math.max(dp[p - 1][j], pre[i] - pre[j]);
11 if (slowest < dp[p][i]) dp[p][i] = slowest;
12 }
13 }
14 }
15 return dp[k - 1][n];
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

painters-partition.ts

1function painterPartition(boards, k) {
2 const n = boards.length;
3 const pre = [0];
4 for (const b of boards) pre.push(pre[pre.length - 1] + b);
5 const dp = Array.from({ length: k }, () => new Array(n + 1).fill(Infinity));
6 for (let i = 1; i <= n; i++) dp[0][i] = pre[i];
7 for (let p = 1; p < k; p++) {
8 for (let i = p + 1; i <= n; i++) {
9 for (let j = p; j < i; j++) {
10 const slowest = Math.max(dp[p - 1][j], pre[i] - pre[j]);
11 if (slowest < dp[p][i]) dp[p][i] = slowest;
12 }
13 }
14 }
15 return dp[k - 1][n];
16}

Where people go wrong

Splitting by COUNT instead of by LOAD. Three painters, so give each a third of the boards: it is the first thing everyone tries, and on ONE natural way of pinning down what a third of the boards means it loses at every one of the seven slider sizes. Cutting into three blocks as equal in count as possible, with any remainder going to the earliest blocks, loses by 10, 9, 6, 10, 6, 5 and 4 from 4 boards up to 10. At 7 boards that rule puts boards 1, 2 and 3 together, 10 and 10 and 5, for 25, against a true optimum of 15. Be careful how much you conclude from that, because the remainder convention is doing some of the work. Send the remainder to the LATEST blocks instead and the same rule ties the optimum at 4 boards; take the best of EVERY cut whose three counts differ by at most one and it ties the optimum at 4 boards and at 10, while still losing by 4, 6, 5, 1 and 5 at the other five sizes. So counting boards is not a good rule with a bad tie-break. It is a rule with no reason to be right that sometimes gets lucky, and the reason is right there in the input: a board's count is always 1, while its length here runs from 2 to 10. The second trap is assuming the heaviest block sits somewhere predictable, usually that the last painter is left the smallest one. It does not. Following the cuts this table picks, the heaviest block is the third at 5, 6 and 10 boards, the second at 7 and 8, the first at 9, and tied across the first two at 4. At the slider's top the last painter carries 25 against 20 and 16. Worse for anyone hoping to name THE optimal cut: at 10 boards four different cuts all score 25, and two of them do leave the last painter the smallest block, so which cut you get is a property of your tie-break and not of the input. The third trap is reading the answer off the wrong axis. Row 2 is three painters and the last column is all the boards, and the answer is the cell where both are true. Further left in row 2 is three painters on a SHORTER job, which answers a different question and is never a LARGER number: strictly smaller from 5 boards up, and at 4 boards the single cell to the left of the answer holds 10 exactly as the answer does. Higher up in the last column is FEWER painters on this job, which is strictly larger at every slider size.

Let k be an input instead of fixing it at 3 painters.
The table gains rows and changes nothing else: k rows, the same prefix-sum row 0, the same min over maxes, the same dots wherever i < p, and the answer at dp[k - 1][n - 1]. Time goes to O(k n^2). This page fixes k at 3 only so the grid stays three rows tall on screen.
Minimize the TOTAL time all the painters spend rather than the slowest painter's time.
The problem disappears. Every board is painted exactly once by exactly one painter, so the total is the sum of all the board lengths, 61 on this page's ten boards, whatever the cuts are, and every legal assignment ties. There is nothing to optimize and no table to build. Make the substitution once anyway: minimizing the MAXIMUM is the whole reason this is a problem, and swapping it for minimizing the sum does not give you an easier version, it gives you a non-problem.
Drop the contiguity requirement, letting a painter take any set of boards.
The recurrence stops working, and it is worth knowing why. "The last painter's block begins after board j" is no longer a decision that leaves a shorter prefix behind, because any board can now go to any painter, so there is no last decision that shrinks the input. What is left is makespan minimization on 3 identical machines, which is NP-hard. Integer board lengths still admit a pseudo-polynomial table, but it is keyed on the loads assigned so far rather than on a prefix length, and the neat 3 by n grid is gone. Contiguity here is the counterpart of adjacency in min-sum-in-a-triangle, and the two do opposite jobs rather than the same one. Drop adjacency there and a small table still WORKS, dp[r][c] = tri[r][c] + the min of the whole row above; what dies is its NECESSITY, since the answer collapses to the sum of the row minima. Drop contiguity here and no small table is possible at all, only the load-keyed pseudo-polynomial one just described. Adjacency is a necessity condition, contiguity a possibility condition, and that difference is worth more than the parallel.

Optimal Strategy for a Game Program for Bridge and Torch problem