Medium Problemsoptimizationgrid

Maximum Tip Calculator

Given n customers in a fixed order and two waiters, where the first waiter can serve at most x of them and the second at most y (with x plus y equal to n), and each customer offers a different tip depending on who serves them, assign every customer to one waiter to maximize the total tip collected.

Do this lesson first: house robber

Example input

n = 9 customers; the first waiter's tips [9, 2, 8, 9, 8, 2, 8, 1, 9], the second waiter's tips [7, 2, 4, 2, 4, 1, 1, 4, 2]; x = 5 and y = 4, the two caps, which add up to the 9 customers

Expected output

56

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][j] is the largest total tip collectable from the FIRST i customers when exactly j of them went to the first waiter. Two numbers name the state, how many customers have been served and how many of those the first waiter took, so the table is a grid even though the two inputs are flat lists. READ THE COLUMN CAREFULLY, because this is the one thing on this page a reader can misread into being unable to read the table at all. THE COLUMN COUNTS ONE WAITER, NOT BOTH. j is the FIRST waiter's share, and the second waiter's share is i - j, which appears nowhere on the screen. Row 6, column 2, which at 9 customers holds 31, is not two customers, it is six: two served by the first waiter and four by the second, and that four is the number you have to subtract to see. WHY THE SUBTRACTION IS LEGAL is worth separating into its two halves, because they come from different parts of the statement and only one of them is about the caps. The half that makes i - j the second waiter's count is simply that EVERY one of the first i customers is served by somebody, so the two waiters' counts add to i; nothing about x or y is needed for that, and it survives making the caps slack. The half that x + y = n buys is narrower and just as useful: with the caps exactly partitioning the customers, row n admits only the split x and y, so the bottom row holds exactly ONE live cell and the answer is a cell rather than a fold across a row. The first two variations below take those two halves away one at a time and they do different damage. The cell holds a TOTAL and nothing about who served whom; if you want the assignment itself you walk the table backwards afterwards, and at 9 customers that walk hands customers 3, 4, 5, 7 and 9 to the first waiter. One more thing the cell does not hold: dp[i][j] is not the best you can do with j slots and i customers to choose from, it is the best you can do having served ALL i of them. Every customer in the first i is assigned to somebody in every arrangement this cell scores, which is why the two arms of the recurrence are a choice between waiters and never a choice to skip.

dp[i][j] = max(dp[i - 1][j - 1] + A[i], dp[i - 1][j] + B[i]), where A[i] and B[i] are what customer i tips the first and the second waiter

Ask who served CUSTOMER i, the last one in the row. Exactly one of the two waiters did, so the two cases are disjoint and between them exhaustive. If the FIRST waiter served customer i, the other i - 1 customers left j - 1 of them to that waiter, and the tip collected on this step is A[i]: that is dp[i - 1][j - 1], the cell up and to the LEFT, plus A[i]. If the SECOND waiter served customer i, the other i - 1 customers left j to the first waiter, unchanged, and the tip is B[i]: that is dp[i - 1][j] directly ABOVE, plus B[i]. Both sub-problems are the same question on a shorter list, so both are final in the table by the time this cell is filled. It is a max rather than a sum because only one of the two things happened and the better of them is wanted, the same reason min-cost-path takes a min over its two neighbours where count-all-paths-in-a-grid adds them. WHICH TIP GOES WITH WHICH CELL IS THE THING TO GET RIGHT, and the rule is short: the step that moves LEFT is the step that grows the first waiter's count, so it carries the first waiter's tip. The diagonal is the first waiter, the vertical is the second. Note also that every candidate here is ITSELF a sum, a cell plus a tip, which is why a cell with only one live arm still comes out as a two-term addition rather than as a bare copy of its neighbour. Both ends of this table have cells with one arm, at column 0 and on the diagonal, and none of them reads differently from the cells with two. Array indexing is worth a word, because the formula above counts customers from 1 while the snippet indexes the tip arrays from 0: row i is CUSTOMER i, so the tip added on that row is a[i - 1], not a[i].

THERE IS EXACTLY ONE BASE, dp[0][0] = 0. No customers served, nobody assigned to either waiter, no tips collected. Every other live cell is computed. TWO SEPARATE SKIP CONDITIONS CARVE THE SHAPE, and both are IMPOSSIBILITY rather than zero. A position with col > row would have the first waiter holding more customers than have been served between the two of them, which is not a hard arrangement to score, it is not an arrangement. A position with row - col > y would leave the second waiter more than their cap of y customers, which the statement forbids outright. A zero in either place would look like a legal assignment worth nothing, when what is actually there is no assignment at all. Nothing is ever written to either kind of position and no live cell reads one, which is why a cell in COLUMN 0 or on the DIAGONAL has ONE genuine candidate rather than one real candidate plus one convenient zero. Those two positions are where an arm is missing, and they are NOT the same thing as the two ends of a row: a row's ends are max(0, i - y) and min(i, x), which coincide with column 0 and the diagonal only while i is at most y. Measured at 9 customers: of the seventeen row-end cells that get computed, nine have one arm and eight have two. Row 5 starts at column 1 rather than column 0, so its left end dp[5][1] = 26 is a row end with both arms, reading dp[4][0] = 15 and dp[4][1] = 22; and dp[9][5] = 56 is both ends of row 9 at once and still reads dp[8][4] = 47 and dp[8][5] = 49. At 4 customers it is four one-armed against three two-armed. Where each condition bites: col > row shaves the TOP RIGHT, so row i stops at column min(i, x); row - col > y shaves the BOTTOM LEFT, so row i starts at column max(0, i - y). What is left is in exact bijection with the pairs of counts inside the two caps, one live cell per (first waiter's count, second waiter's count) with both inside their own cap, so the live cells number (x + 1) times (y + 1) inside the (n + 1) times (x + 1) rectangle the grid declares. Recount that by driving the spec at a slider size and counting its writes against the declared shape rather than trusting the formula. THE DOTS ARE NOT ZEROS, and this page is unusual in how much it would GET AWAY WITH if they were, which is worth measuring rather than borrowing another page's alarm. min-sum-in-a-triangle takes a min over sums, so a zero above its diagonal is a free cheap number the descent gladly cheats through and its answer comes out below the truth. This page takes a MAX over sums of positive tips, so a zero is the least attractive thing a phantom position could offer: it can only win where the honest candidate is smaller, and every honest candidate here is a non-negative running total plus a positive tip. Measured at every one of the six slider sizes: fill the whole rectangle with no skip at all, let each phantom position compute from its neighbours, and the answer cell is unchanged, 26, 34, 35, 43, 47 and 56. The only phantom positions a live cell could even read are the ones just above the diagonal, at (i - 1, i), read by the diagonal cell (i, i); the bottom left region is unreachable outright, because a position at (r, c) with r - c > y is read only by (r + 1, c) and (r + 1, c + 1), and both of those are further past the same cap. NOW STATE THE MARGIN, because the margin is what makes that a fact about these numbers rather than a guarantee. At 9 customers the diagonal cells dp[1][1], dp[2][2], dp[3][3], dp[4][4] and dp[5][5] beat their phantom zero by 2, 9, 15, 26 and 32. The 2 at dp[1][1] is the whole of the safety margin at the top of the table, and it is exactly A[1] - B[1], nine against seven; had customer 1 tipped the second waiter more than the first, the phantom zero would have won that cell outright. So the correctness of this table rests on the position not existing, NOT on the operator being forgiving. Filling row-major, left to right within each row, needs one ordering property and has it: both cells a computed cell reads sit in the row ABOVE, never in its own row, so the previous row being finished is the whole requirement and the order within a row is free.

Tabulation over the live cells, one row-major sweep. WHY TWO AXES AND NOT THREE is the method this page exists to show, and it pays to be exact about which part of the statement each axis rests on, because the two are easy to run together. The second waiter's count is i - j because every one of the first i customers is served by somebody; that is what removes the third number, and it holds whatever the caps are. The statement's x + y = n then does a second, separate job: because the caps exactly partition the customers, row n admits the single split x and y, so the answer is one named cell rather than the largest entry of the bottom row. Take the general move away rather than either detail: before adding an axis to a state, check whether something you were already given determines it. MEMOIZATION SKIPS NOTHING HERE, and that is a measurement rather than a slogan, because on several pages in this course it skips a great deal. Descend from the answer cell dp[n][x] through the two arms and the cone reaches EVERY live cell, at all six slider sizes, so a top-down solve visits exactly the states the sweep does and pays call overhead on top. Recount that by driving the spec, listing the live cells, and walking both arms back from the answer cell. The reason is the shape: the answer needs all n customers served with both caps exactly full, so every live cell extends to a complete assignment and there is no live cell that leads nowhere. COST. One max of AT MOST two candidates per live cell, so O(n x) time and O(n x) space, which at this page's x = ceil(n / 2) is quadratic in the number of customers. A cell reads only the row above, at its own column and one to the left, so one rolling row of x + 1 entries is enough, provided you sweep j DOWNWARDS so the value one column left is still the previous row's when you reach it; checked against the full table at every slider size. THE TABLE IS NOT THE CHEAPEST ROUTE TO THIS ANSWER, and saying so is more useful than hiding it. Write the total as the sum of EVERY customer's second-waiter tip, plus, for each customer handed to the first waiter, the MARGIN A[i] - B[i]. That identity is exact: B[i] is collected whoever serves customer i, and the first waiter adds A[i] - B[i] on top of it. Since the caps force exactly x customers to the first waiter, the best total is the sum of all the B tips plus the x LARGEST margins, and no table is needed at all. Measured against brute force at every slider size, sorting by margin and taking the top x returns 26, 34, 35, 43, 47 and 56, right every time, and at 9 customers it picks customers 3, 4, 5, 7 and 9, the same set the table's own backward walk reconstructs. So the table is the DERIVATION and the sort is the shortcut you take once you believe it. State the bound with it, because the bound is the point: the argument needs each customer's contribution to depend on nobody but themselves, and the last variation below breaks exactly that. The table survives it for the price of one extra bit of state; the sort does not survive it at all.

Time O(n × x), one max of at most two candidates per live cell, with (x + 1) × (y + 1) live cells inside the (n + 1) × (x + 1) rectangle the grid declaresSpace O(n × x), reducible to O(x) with one rolling row swept right to left

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.

THERE IS EXACTLY ONE BASE, dp[0][0] = 0. No customers served, nobody assigned to either waiter, no tips collected. Every other live cell is computed. TWO SEPARATE SKIP CONDITIONS CARVE THE SHAPE, and both are IMPOSSIBILITY rather than zero. A position with col > row would have the first waiter holding more customers than have been served between the two of them, which is not a hard arrangement to score, it is not an arrangement. A position with row - col > y would leave the second waiter more than their cap of y customers, which the statement forbids outright. A zero in either place would look like a legal assignment worth nothing, when what is actually there is no assignment at all. Nothing is ever written to either kind of position and no live cell reads one, which is why a cell in COLUMN 0 or on the DIAGONAL has ONE genuine candidate rather than one real candidate plus one convenient zero. Those two positions are where an arm is missing, and they are NOT the same thing as the two ends of a row: a row's ends are max(0, i - y) and min(i, x), which coincide with column 0 and the diagonal only while i is at most y. Measured at 9 customers: of the seventeen row-end cells that get computed, nine have one arm and eight have two. Row 5 starts at column 1 rather than column 0, so its left end dp[5][1] = 26 is a row end with both arms, reading dp[4][0] = 15 and dp[4][1] = 22; and dp[9][5] = 56 is both ends of row 9 at once and still reads dp[8][4] = 47 and dp[8][5] = 49. At 4 customers it is four one-armed against three two-armed. Where each condition bites: col > row shaves the TOP RIGHT, so row i stops at column min(i, x); row - col > y shaves the BOTTOM LEFT, so row i starts at column max(0, i - y). What is left is in exact bijection with the pairs of counts inside the two caps, one live cell per (first waiter's count, second waiter's count) with both inside their own cap, so the live cells number (x + 1) times (y + 1) inside the (n + 1) times (x + 1) rectangle the grid declares. Recount that by driving the spec at a slider size and counting its writes against the declared shape rather than trusting the formula. THE DOTS ARE NOT ZEROS, and this page is unusual in how much it would GET AWAY WITH if they were, which is worth measuring rather than borrowing another page's alarm. min-sum-in-a-triangle takes a min over sums, so a zero above its diagonal is a free cheap number the descent gladly cheats through and its answer comes out below the truth. This page takes a MAX over sums of positive tips, so a zero is the least attractive thing a phantom position could offer: it can only win where the honest candidate is smaller, and every honest candidate here is a non-negative running total plus a positive tip. Measured at every one of the six slider sizes: fill the whole rectangle with no skip at all, let each phantom position compute from its neighbours, and the answer cell is unchanged, 26, 34, 35, 43, 47 and 56. The only phantom positions a live cell could even read are the ones just above the diagonal, at (i - 1, i), read by the diagonal cell (i, i); the bottom left region is unreachable outright, because a position at (r, c) with r - c > y is read only by (r + 1, c) and (r + 1, c + 1), and both of those are further past the same cap. NOW STATE THE MARGIN, because the margin is what makes that a fact about these numbers rather than a guarantee. At 9 customers the diagonal cells dp[1][1], dp[2][2], dp[3][3], dp[4][4] and dp[5][5] beat their phantom zero by 2, 9, 15, 26 and 32. The 2 at dp[1][1] is the whole of the safety margin at the top of the table, and it is exactly A[1] - B[1], nine against seven; had customer 1 tipped the second waiter more than the first, the phantom zero would have won that cell outright. So the correctness of this table rests on the position not existing, NOT on the operator being forgiving. Filling row-major, left to right within each row, needs one ordering property and has it: both cells a computed cell reads sit in the row ABOVE, never in its own row, so the previous row being finished is the whole requirement and the order within a row is free.

row i: the first i customers, all of them served by one waiter or the other

0

1

2

3

4

5

0

·

1

7

9

·

2

9

11

·

3

13

17

19

·

4

15

22

26

28

·

5

·

26

30

34

36

6

·

31

35

37

38

7

·

39

43

45

8

·

47

49

9

·

56

column j: how many of those i went to the FIRST waiter, so the second waiter took i - j and that number is nowhere on this table

maximum-tip-calculator.ts

1function maxTip(a, b, x, y) {
2 const n = a.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(x + 1).fill(-Infinity));
4 dp[0][0] = 0;
5 for (let i = 1; i <= n; i++) {
6 for (let j = Math.max(0, i - y); j <= Math.min(i, x); j++) {
7 const byFirst = j > 0 ? dp[i - 1][j - 1] + a[i - 1] : -Infinity;
8 const bySecond = j < i ? dp[i - 1][j] + b[i - 1] : -Infinity;
9 dp[i][j] = Math.max(byFirst, bySecond);
10 }
11 }
12 return dp[n][x];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

maximum-tip-calculator.ts

1function maxTip(a, b, x, y) {
2 const n = a.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(x + 1).fill(-Infinity));
4 dp[0][0] = 0;
5 for (let i = 1; i <= n; i++) {
6 for (let j = Math.max(0, i - y); j <= Math.min(i, x); j++) {
7 const byFirst = j > 0 ? dp[i - 1][j - 1] + a[i - 1] : -Infinity;
8 const bySecond = j < i ? dp[i - 1][j] + b[i - 1] : -Infinity;
9 dp[i][j] = Math.max(byFirst, bySecond);
10 }
11 }
12 return dp[n][x];
13}

Where people go wrong

Giving each customer to whoever tips them more, TIES TO THE FIRST WAITER, then handing the rest to the other waiter once one of them hits their cap. It is the natural first instinct and it loses at every size this page can show: 17 against 26, 25 against 34, 26 against 35, 34 against 43, 38 against 47 and 44 against 56, a gap of 9 at the first five sizes and 12 at the sixth. The tie-break has to be named rather than assumed, because customer 2 is worth exactly 2 to each waiter, so "whoever tips them more" decides nothing there and those six figures are the tie-to-first reading. Send the tie to the second waiter instead and every figure moves, to 21, 32, 33, 38, 42 and 45; the rule still loses at all six sizes, which is the part this page rests on. WHY IT LOSES IS NOT THAT GREED IS WRONG HERE, and getting that right is worth more than the pitfall itself. A greedy rule does solve this problem exactly, as the execution note works out; the instinct just reaches for the WRONG greedy rule. Asking whether A[i] beats B[i] uses only the SIGN of the margin A[i] - B[i] and throws away its SIZE, and the sizes are what matter, because the first waiter's slots are scarce and should go to the customers the first waiter is worth the most EXTRA on. At 9 customers the margins run 2, 0, 4, 7, 4, 1, 7, -3, 7 across customers 1 to 9. The five largest sit at customers 3, 4, 5, 7 and 9, which is exactly the set the table picks. The sign rule instead walks left to right and fills the cap with customers 1 to 5, two of whom, customers 1 and 2, have margins of 2 and 0; by the time customers 7 and 9 arrive, each worth 7 more to the first waiter, there is no slot left. That is 36 on the first waiter and 8 on the second for 44, against the table's 42 and 14 for 56. The two assignments differ by a single two-for-two swap: move customers 1 and 2 out of the first waiter's five and customers 7 and 9 in, and that side gains 6; the second waiter then takes 1 and 2 in place of 7 and 9 and gains 6 as well. Twice 6 is the whole of the 12. THE SECOND TRAP IS READING THE COLUMN AS A CUSTOMER COUNT. It is one WAITER'S customer count. dp[6][2] = 31 at 9 customers is six customers served, two by the first waiter and four by the second; it is not two customers, and it is not four either. Every cell's value totals the tips of all i customers in its row, never just the j in its column. The third trap is treating the shape as the lower triangle those other 2D pages use. It is a triangle shaved at BOTH ends, one condition per end, and the two ends are shaved for different reasons: col > row is arithmetic nonsense, more customers with one waiter than have been served at all, while row - col > y is a real assignment that a stated cap forbids. Only the second one moves as the caps move. This shape does protect you against the classic index swap better than a full rectangle would, and the reason is exact rather than lucky: a live cell off the diagonal has col < row, so the swapped position has col > row and is never a live cell, at any slider size. WHERE it lands depends on the row rather than on the slider: while the row is at most x the swap is a dot inside the table, and past that the column index runs off the declared width altogether. Measured at 9 customers, of the 24 live off-diagonal cells 14 transpose to a dot and 10, every one of them in rows 6 to 9, transpose off a table that has only 6 columns; at 4 customers it is 3 and 3. The answer cell dp[9][5] is one of those ten, its transpose dp[5][9] landing outside the declared columns, but nothing there is special to the answer cell.

Make the caps SLACK, x + y > n, with every customer still served.
The state does not change at all, and that is the point worth taking from this variation rather than the arithmetic. i - j is still the second waiter's count, for the reason it always was: everybody is served, so the two counts add to the row index. What changes is the SHAPE and the ANSWER CELL. The bottom left condition now reads row - col > y for a larger y, so it shaves less, and row n gains live cells; the answer becomes the largest cell of the bottom row rather than a named one. Measured with both caps set to ceil(n / 2), which is slack at the odd sizes and exactly tight at the even ones: at 5 customers the bottom row holds dp[5][2] = 30 beside dp[5][3] = 34, at 7 it holds dp[7][3] = 39 beside dp[7][4] = 43, and at 9 it holds dp[9][4] = 52 beside dp[9][5] = 56, the larger matching brute force each time. Look hard at that 52. It is not junk and it is not a phantom; it is the exact best total if the second waiter took five customers instead of four, sitting one column from the answer and looking every bit like a competitor. On this page it is a dot, because the cap forbids it.
Make the caps too small to cover everybody, x + y < n, so some customers go unserved.
THIS is where the state genuinely needs a third number, and it is a sharper break than the slack version. The row index stops counting customers SERVED and starts counting customers CONSIDERED, so i - j is no longer the second waiter's count and has to be carried in its own axis: dp[i][j][k], with a third arm for leaving customer i unserved. Nothing about the sweep or the ordering changes, but the table is a cube. Measured with both caps set to floor(n / 3), so at 9 customers each waiter may take 3 and six of the nine get served at all, the best total is 41 against this page's 56. The margin argument in the execution note stops applying, and it is worth being exact about why rather than guessing either way: that sort rests on exactly x customers going to the first waiter and ALL the rest to the second, which is what let the total be written as the B tips plus x margins. Here neither of those holds, so whether some other sort works is an open question this page does not answer.
Add a third waiter, with caps x + y + z = n.
The same determination applies once more and buys the same thing: name the customers served and any two waiters' counts, and the third waiter's count is forced. So the state grows by ONE axis rather than two and the recurrence grows a third arm, one per waiter who could have served customer i. The cube is (n + 1) by (x + 1) by (y + 1) declared with (x + 1) times (y + 1) times (z + 1) of it live, which at 9 customers and caps of 3, 3 and 3 is 160 declared against 64 live. It is no longer a two-axis table, which is why this is a variation rather than a slider setting on this page.
Let what customer i tips depend on which waiter served customer i - 1.
The MARGIN SHORTCUT DIES OUTRIGHT, and it is the only variation here that kills it. Its identity needs each customer's contribution to depend on nobody but themselves, and this breaks that from the SECOND customer on, since customer 1 has no predecessor for their tip to depend on, so there is nothing left to sort. The table survives, and cheaply: add one bit to the state for who served customer i - 1, which is two tables of this exact shape side by side, twice the cells, and each of the two arms splits into two according to that bit, so four candidates instead of two. The row-major sweep, the fill order and both skip conditions are untouched. That asymmetry is the transferable part: a constraint reaching one step back costs a table a bit of state, while it costs a sorting argument the whole argument.

Floyd Warshall Algorithm