Medium Problemscountinggridcombinatorics

Tile Stacking Problem

Given n tiles arranged in a row, each to be painted with one of m available colors, count the colorings in which no more than k consecutive tiles share the same color.

Do this lesson first: climbing stairs

Example input

n = 8 tiles, m = 3 colours, k = 3 as the longest run allowed

Expected output

5676

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][j] is the number of ways to colour the first r + 1 tiles from the 3 colours so that no run of one colour anywhere among them is longer than 3 AND the run the tiles FINISH on is at most j long. THE ROW INDEX IS ONE LESS THAN THE TILE COUNT: row 0 is 1 tile, row r is r + 1 tiles, so the table declares size rows rather than size + 1, because a row of no tiles answers nothing anybody asked. Two numbers name the state, how many tiles have been coloured and how long a run they are allowed to finish on, so the table is a grid even though the input is a single number and there is no array anywhere on this page. AT MOST IS THE LOAD-BEARING PHRASE, AND IT IS NOT A TRICK. The state you would write down first is exactly j, the colourings whose final run has length precisely j, and it is a perfectly good state with a perfectly good recurrence. Its answer, though, is the SUM of the bottom row rather than any one cell of it, because a legal colouring of the whole row ends on a run of 1, 2 or 3 and all three count. This page reports one highlighted cell, so a total across a row is not something it can point at. Making the state cumulative fixes that at no cost: once a cell counts every final run up to j, the cell at j = 3 has already done the summing, and dp[size - 1][3] IS the answer outright. Three separate measurements back that up rather than one. The cumulative table equals the running row-total of the exact-run table, cell for cell, at every size the slider offers; the exact-run table's bottom row sums to the same answer as the cumulative table's last cell at every one of those sizes; and the cumulative recurrence was checked against brute-force enumeration of all 3^n colourings at every n from 1 to 9, agreeing exactly. THAT REFORMULATION IS THE TRANSFERABLE PART OF THIS PAGE and it is worth more than the recurrence. Whenever the natural answer is a fold across a row, look for an axis along which at most is meaningful and push the fold into the state. The axis here is a LENGTH, which is ordered, so the move is available. It is not always available: an axis of unordered labels, a colour or a common difference, has no at most to accumulate along, and a page whose answer folds over such an axis cannot be rescued this way. Two smaller things the cell does NOT hold. It holds a count, so nothing here tells you which tile got which colour. And column 1 is NOT no two neighbours ever match: it is every legal colouring whose last two tiles differ, with the tiles before them free to run up to 3. Those are different questions and different numbers, 3888 against 384 at 8 tiles, and running them together is the easiest wrong reading of this axis.

dp[r][j] = (m - 1) * dp[r - 1][k] + dp[r - 1][j - 1], which at m = 3 and k = 3 is 2 * dp[r - 1][3] + dp[r - 1][j - 1]

Ask what the LAST tile of the row does. It either takes a different colour from the tile before it or it repeats that colour. Every colouring does exactly one of those two things, so the two cases are disjoint and together exhaustive and their counts add. TAKE THE REPEAT CASE FIRST, because it is the one with no multiplier. If the last tile repeats, the run it joins is one longer than the run the shorter row ended on, so that shorter run had to be at most j - 1 long for this one to come in at at most j. There are dp[r - 1][j - 1] colourings of the first r tiles that finish that way, and each of them yields exactly ONE colouring of r + 1 tiles: the colour is forced, it is the one already there, and there is nothing left to choose. So this case contributes dp[r - 1][j - 1] as it stands. NOW THE CHANGE CASE, WHICH IS WHERE THE COEFFICIENT COMES FROM. If the last tile takes a different colour it starts a fresh run of length 1, and 1 is at most j for every column this table computes, so the new run cannot be the thing that breaks the rule. What came before is therefore under NO constraint beyond being legal in its own right, and legal in its own right is exactly what column k holds: dp[r - 1][3] is every colouring of the first r tiles, whatever run it ends on. Each of those can be followed by any of the m - 1 = 2 colours that are not the one on tile r, and each choice is a DIFFERENT colouring, so this case contributes 2 × dp[r - 1][3], not dp[r - 1][3]. Nothing is double counted either: given a colouring of r + 1 tiles whose last two tiles differ, delete the last tile and you recover both the shorter colouring and which of the two other colours was used, uniquely. WHY m - 1 AND NOT m: the last tile is choosing a colour DIFFERENT from its neighbour, so one of the three is ruled out. Use 3 and the answers come out 189, 747, 2952, 11664 and 46089 across 4 to 8 tiles against the true 78, 228, 666, 1944 and 5676, wrong at every size and off by a factor of more than eight at the top. AND WHY THE FACTOR SITS ON THE COLUMN-3 CELL rather than on the column-j one: reach for dp[r - 1][j] instead and you have quietly required the earlier run to be short as well, which the change case does not require. That is the dangerous mistake on this page, because it is RIGHT at 4 tiles, returning 78, and wrong at the other four sizes, returning 216, 576, 1488 and 3744. It is a SUM between the two cases and a PRODUCT inside one of them because this is a counting problem: both cases really happen, across different colourings, and the total of them is wanted rather than the better of them. That is the same distinction count-all-paths-in-a-grid draws against min-cost-path. ways-to-partition-a-set is the other page in this course where one branch contributes several outcomes per shorter arrangement rather than one, and the two coefficients are worth telling apart: there the multiplier is the COLUMN index and changes as you walk right, here it is the constant m - 1 and never moves.

THE WHOLE OF ROW 0 IS GIVEN, and so is the whole of column 0. Row 0 is 0, 3, 3, 3. A single tile has 3 colourings, its run is exactly 1 long, so it satisfies at most j for every j from 1 up and none at all at j = 0. Row 0 is given rather than summed for the plainest reason there is: there is no row above it to read. Get its scale wrong and the whole table scales with it, because every cell is linear in row 0. Write 0, 1, 1, 1 there, on the theory that one tile is one way to colour a tile, and the answers come out 26, 76, 222, 648 and 1892 across 4 to 8 tiles, which is exactly one third of the truth at every size. Write 3, 3, 3, 3, letting the impossible column 0 carry a 3 as well, and they come out 81, 234, 684, 1998 and 5832, above the truth at every size. dp[r][0] = 0 for every row past the first. No colouring of a non-empty row of tiles finishes on a run of length at most 0, because it finishes on a run of at least 1. That 0 has to be a BASE rather than a computed cell for two separate reasons and both matter. Arithmetically, dp[r][0] would reach for dp[r - 1][-1], column -1, which is off the table altogether. Editorially, a cell with only one live term would narrate as a bare restatement of another cell, matching none of the arithmetic forms this course narrates in, so it would need writing by hand anyway. And that column is not decorative: every computed cell in column 1 reads it, which is what makes column 1 read 2 × dp[r - 1][3] + 0 and nothing else. The 0 in that sum is a real case that cannot happen, not a term somebody forgot. Getting that edge wrong is quiet at the slider's minimum and loud after it, which is worth measuring rather than guessing at. Copy it across as a 3 and the answers come out 78, 231, 675, 1971 and 5757 across 4 to 8 tiles: EXACTLY RIGHT at 4 tiles and wrong at the other four. Copy it across as a 1 and they come out 78, 229, 669, 1953 and 5703, right at 4 tiles again. The reason is a propagation delay rather than luck: a wrong column-0 cell corrupts column 1 one row down, column 2 the row after that and column 3 only on the third row, so at 4 tiles the damage has not reached the answer cell yet. THE FIRST TERM IS THE SAME CELL FOR EVERY CELL IN THE ROW, which is this table's one genuinely unusual property. dp[r - 1][3] does not merely look like the other cells' first dependency, it IS it: at 8 tiles the whole of row 7 multiplies the same 1944. Recount that by driving the spec at any size and listing each computed cell's first dependency, which is column 3 in every row. Two consequences. A row costs three multiplications by one shared number plus three additions of the neighbour one column to the left, so the multiplication hoists straight out of the inner loop. And the arrows fan out of a single cell rather than tracking each cell they feed, which is what the animation shows. THERE IS NO SKIP AND NOT A SINGLE DOT ON THIS PAGE, unlike the triangular tables in this course that declare a square and skip everything above the diagonal. Every declared cell is live, which the shape makes plain: 4 columns times size rows declared, size + 3 of them given (the 4 in row 0 plus one per row below it in column 0) and 3 times (size - 1) computed, so at the slider's maximum of 8 tiles that is 32 declared, 11 given and 21 computed. Filling row-major, left to right within each row, needs only one ordering property and has it: both cells a computed cell reads sit in the row ABOVE, never in its own row and never below, so the previous row being finished is the whole requirement and the left-to-right order within a row is free.

Tabulation, one row-major sweep, and here the table really is rescuing an exponential, which is not true of every counting page in this course. The independent check behind this page builds all 3^n colourings and filters them, which is 6561 colourings at 8 tiles against the 21 cells this sweep computes at the same size, and 3^n keeps growing while 3 times (n - 1) does not. COST. The table is n rows by k + 1 columns with one multiply and one add per cell, so O(n k) time and O(n k) space. A cell only ever reads the row above, so one rolling row of k + 1 entries is enough; and because every cell of a row wants the SAME entry of the previous row, you can overwrite that row in place provided you save dp[r - 1][k] into a scalar first and then sweep j downwards, so the old value one column left is still there when you need it. That is O(k) space, which at a fixed k = 3 is a handful of variables. Memoization has almost nothing to skip here, and that is a measurement rather than a slogan, because on several pages in this course it skips a great deal. Descend from dp[n - 1][k] and the cone covers every cell of the table except a STAIRCASE OF SIX at the left end of the last three rows: measured at every size the slider offers, the six are always the same shape, three of them column-0 bases and three of them computed cells, because nothing reads the bottom row except the answer itself. So a memoized solve computes 3n - 6 cells against the sweep's 3n - 3, a ratio running 1.500, 1.333, 1.250, 1.200 and 1.167 from 4 tiles up to 8 and falling towards 1 rather than growing. There is no surplus worth a cache here, and the rolling row is a real advantage a cache cannot have. THE ROW IS CHEAP AND THE ROW IS ALSO INFORMATIVE. Every cell of the sweep is a finished answer for its own tile count and its own final-run bound, and so are the differences along a row: dp[r][j] minus dp[r][j - 1] is the number of colourings whose final run is EXACTLY j, verified cell for cell against a directly built exact-run table at every size the slider offers. At the bottom of the 8-tile table those differences read 3888, 1332 and 456, and they add back to 5676. SURVIVING A CHANGE, and the one place a table is not needed at all. The answers 3, 9, 27, 78, 228, 666, 1944 and 5676 satisfy a(n) = 2 × (a(n - 1) + a(n - 2) + a(n - 3)), which is climbing-stairs-three-moves' shape with a coefficient bolted on, and it collapses the whole table into three running scalars. State that with its bound rather than as a slogan, because the bound is where it goes wrong: it holds from n = 4 onwards and FAILS at n = 3, giving 26 against the true 27. The reason is exact. Each term stands for the final run being 1, 2 or 3 tiles long, and for a run shorter than the whole row the tile before it fixes a colour to avoid, which is the factor of 2; but a run that covers the entire row has no tile before it and so has 3 choices, not 2, and that case exists only while n is at most k. The identity also stops being available the moment m or k stops being a constant, since it is k terms wide with a coefficient of m - 1 baked in, whereas the table only changes shape. So the table is the derivation and the k-term recurrence is the shortcut you take once you believe the derivation.

Time O(n × k) to fill the table, one multiply and one add per cell, so 3 × (n - 1) computed cells at k = 3Space O(n × k), reducible to O(k) 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.

THE WHOLE OF ROW 0 IS GIVEN, and so is the whole of column 0. Row 0 is 0, 3, 3, 3. A single tile has 3 colourings, its run is exactly 1 long, so it satisfies at most j for every j from 1 up and none at all at j = 0. Row 0 is given rather than summed for the plainest reason there is: there is no row above it to read. Get its scale wrong and the whole table scales with it, because every cell is linear in row 0. Write 0, 1, 1, 1 there, on the theory that one tile is one way to colour a tile, and the answers come out 26, 76, 222, 648 and 1892 across 4 to 8 tiles, which is exactly one third of the truth at every size. Write 3, 3, 3, 3, letting the impossible column 0 carry a 3 as well, and they come out 81, 234, 684, 1998 and 5832, above the truth at every size. dp[r][0] = 0 for every row past the first. No colouring of a non-empty row of tiles finishes on a run of length at most 0, because it finishes on a run of at least 1. That 0 has to be a BASE rather than a computed cell for two separate reasons and both matter. Arithmetically, dp[r][0] would reach for dp[r - 1][-1], column -1, which is off the table altogether. Editorially, a cell with only one live term would narrate as a bare restatement of another cell, matching none of the arithmetic forms this course narrates in, so it would need writing by hand anyway. And that column is not decorative: every computed cell in column 1 reads it, which is what makes column 1 read 2 × dp[r - 1][3] + 0 and nothing else. The 0 in that sum is a real case that cannot happen, not a term somebody forgot. Getting that edge wrong is quiet at the slider's minimum and loud after it, which is worth measuring rather than guessing at. Copy it across as a 3 and the answers come out 78, 231, 675, 1971 and 5757 across 4 to 8 tiles: EXACTLY RIGHT at 4 tiles and wrong at the other four. Copy it across as a 1 and they come out 78, 229, 669, 1953 and 5703, right at 4 tiles again. The reason is a propagation delay rather than luck: a wrong column-0 cell corrupts column 1 one row down, column 2 the row after that and column 3 only on the third row, so at 4 tiles the damage has not reached the answer cell yet. THE FIRST TERM IS THE SAME CELL FOR EVERY CELL IN THE ROW, which is this table's one genuinely unusual property. dp[r - 1][3] does not merely look like the other cells' first dependency, it IS it: at 8 tiles the whole of row 7 multiplies the same 1944. Recount that by driving the spec at any size and listing each computed cell's first dependency, which is column 3 in every row. Two consequences. A row costs three multiplications by one shared number plus three additions of the neighbour one column to the left, so the multiplication hoists straight out of the inner loop. And the arrows fan out of a single cell rather than tracking each cell they feed, which is what the animation shows. THERE IS NO SKIP AND NOT A SINGLE DOT ON THIS PAGE, unlike the triangular tables in this course that declare a square and skip everything above the diagonal. Every declared cell is live, which the shape makes plain: 4 columns times size rows declared, size + 3 of them given (the 4 in row 0 plus one per row below it in column 0) and 3 times (size - 1) computed, so at the slider's maximum of 8 tiles that is 32 declared, 11 given and 21 computed. Filling row-major, left to right within each row, needs only one ordering property and has it: both cells a computed cell reads sit in the row ABOVE, never in its own row and never below, so the previous row being finished is the whole requirement and the left-to-right order within a row is free.

row r: holds r + 1 tiles, so row 0 is one tile and the bottom row is all of them

0

1

2

3

0

3

1

0

6

9

2

0

18

24

27

3

0

54

72

78

4

0

156

210

228

5

0

456

612

666

6

0

1332

1788

1944

7

0

3888

5220

5676

column j: the bound on the run the tiles finish on, so the cell counts legal colourings whose final run is AT MOST j long

tile-stacking.ts

1function tileStacking(n, m, k) {
2 const dp = Array.from({ length: n }, () => new Array(k + 1).fill(0));
3 for (let j = 1; j <= k; j++) dp[0][j] = m;
4 for (let r = 1; r < n; r++) {
5 dp[r][0] = 0;
6 for (let j = 1; j <= k; j++) {
7 const changedColour = (m - 1) * dp[r - 1][k];
8 const repeatedColour = dp[r - 1][j - 1];
9 dp[r][j] = changedColour + repeatedColour;
10 }
11 }
12 return dp[n - 1][k];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

tile-stacking.ts

1function tileStacking(n, m, k) {
2 const dp = Array.from({ length: n }, () => new Array(k + 1).fill(0));
3 for (let j = 1; j <= k; j++) dp[0][j] = m;
4 for (let r = 1; r < n; r++) {
5 dp[r][0] = 0;
6 for (let j = 1; j <= k; j++) {
7 const changedColour = (m - 1) * dp[r - 1][k];
8 const repeatedColour = dp[r - 1][j - 1];
9 dp[r][j] = changedColour + repeatedColour;
10 }
11 }
12 return dp[n - 1][k];
13}

Where people go wrong

Using the exact-run state and then forgetting to sum the bottom row. Build dp[r][j] as the final run is EXACTLY j long instead of at most j and you still have a correct table answering a real question, with the same shape, the same row-major fill order and whole numbers throughout. THE ARROWS ARE THE ONE THING THAT DOES CHANGE, and they are the tell. Column 1 has to read the WHOLE of the row above rather than one cell of it, because a fresh run of length 1 can follow any legal colouring whatever run it ended on, and the exact-run state has no single cell holding that total the way this page's column 3 does; columns 2 and 3 then read exactly ONE cell each, since a run of exactly j extends a run of exactly j - 1 and nothing else. Measured, that is a fan of 3, 1, 1 across the row against this page's uniform 2, so the dependency picture is neither two arrows nor even the same count from one cell to the next. The fold this page pushed into its state has to happen somewhere, and in the exact-run table it happens in that column-1 fan. Do not try to keep both halves either. Hold on to this page's two arrows while switching to exact-run bases and what you get is not a different correct answer, it is nonsense: measured down five tiles it reads 0 3 0 0, then 0 0 3 0, then 0 0 0 3, then 0 6 6 6, then 0 12 18 18, against the true exact table's 0 3 0 0, then 0 6 3 0, then 0 18 6 3, then 0 54 18 6, then 0 156 54 18. So the arithmetic is where this mistake hides and the arrows are where you catch it. Now its cost. Read the answer off the bottom right cell of the genuine exact-run table the way this page does, and you have reported the colourings that end in a run of exactly 3 rather than all of them. Measured, that returns 6, 18, 54, 156 and 456 across 4 to 8 tiles against the true 78, 228, 666, 1944 and 5676, which is between 7.6 and 8.2 per cent of the truth at every one of those five sizes. Three things let it survive a glance. FIRST, the wrong answers are a recognisable sequence rather than obvious garbage, and they are not small enough to look broken. SECOND, and worse, every one of them is a number that appears on the CORRECT table: at all five sizes the wrong answer sits in column 1 exactly two rows above the bottom, and it is also exactly twice the true answer three sizes down, so a reader checking it against the picture or against a smaller run can find it and be reassured. THIRD, the sibling mistake of reading column 1 of the exact table is invisible for a stronger reason still: the exact and the cumulative tables AGREE throughout column 1, because at most 1 and exactly 1 are the same thing once column 0 is 0, so that read lands on a genuine cell of this page's own table, the 3888 at 8 tiles. The fix is not to sum more carefully. It is to notice that a fold across a row can be pushed into the state, which is what at most does. The second mistake is which cell the coefficient multiplies, and it is dangerous because it is right at the smallest size the slider offers. Write 2 × dp[r - 1][j] + dp[r - 1][j - 1], reading straight up instead of across to column 3, and the answers come out 78, 216, 576, 1488 and 3744: exactly right at 4 tiles and wrong at the other four. That is why the check behind this page runs every size the slider offers rather than one. The other three index and constant mistakes are loud rather than quiet, and they are worth separating from the quiet ones for exactly that reason. Swap the two terms so the diagonal neighbour is the one multiplied and it reads 57, 147, 369, 891 and 2217, wrong everywhere and below the truth. Drop the coefficient altogether and it reads 21, 39, 72, 132 and 243, wrong everywhere and further below. Use m instead of m - 1 and it reads 189, 747, 2952, 11664 and 46089, wrong everywhere and above. The last mistake is reading the two axes the wrong way round, and this table protects you against it less than the triangular pages do, because every declared cell here is live and a swapped lookup lands on a real number rather than on a dot. It does not always land at all: at 8 tiles the answer is dp[7][3] and the transposed dp[3][7] is off the table, since the table is only 4 columns wide however many rows it has. Inside the top left 4 by 4 corner the swap is silent, though. dp[1][3] is 9 and dp[3][1] is 54, and both are perfectly good counts of something else.

Change k, the longest run allowed, keeping m = 3 colours.
The table gets k + 1 columns instead of 4 and nothing else about it moves: the factor is still m - 1, row 0 is still m in every column from 1 rightwards and 0 at column 0, column 0 is still 0 all the way down, the first term still reads the LAST column of the row above, and the answer is still the bottom right cell. Measured against brute force at 4 to 8 tiles, k = 1 gives 24, 48, 96, 192 and 384; k = 2 gives 66, 180, 492, 1344 and 3672; this page's k = 3 gives 78, 228, 666, 1944 and 5676; k = 4 gives 81, 240, 714, 2124 and 6318. Both ends of that range are worth naming. At k = 1 the table is two columns wide and dp[r][1] = 2 × dp[r - 1][1] + 0, so the sweep degenerates into a doubling and the answer is 3 × 2^(n - 1) in closed form, which is why no two neighbours match needs no table at all. At k at least n the rule cannot bite and the answer is plainly 3^n: k = 4 at 4 tiles returns 81, which is 3^4, while k = 4 at 5 tiles returns 240 rather than 243, the three missing colourings being the all-one-colour rows.
Change m, the number of colours, keeping k = 3.
Two constants move and nothing structural does. The factor becomes m - 1 and row 0 becomes m in every column from 1 rightwards; the shape, the base positions, the fill order and both dependency arrows are untouched. Measured against brute force at 4 to 8 tiles, m = 2 gives 14, 26, 48, 88 and 162; this page's m = 3 gives 78, 228, 666, 1944 and 5676; m = 4 gives 252, 996, 3936, 15552 and 61452; m = 5 gives 620, 3080, 15300, 76000 and 377520. The cumulative recurrence was checked against brute-force enumeration across every combination of m from 2 to 5 with k from 1 to 4 at every n from 1 to 8, and it agrees at all of them, so neither constant is doing anything special at 3.
Ask how many colourings end in a run of EXACTLY j tiles rather than at most j.
Nothing about the recurrence, the bases or the fill order moves, and no second sweep is needed: the answer is dp[r][j] minus dp[r][j - 1], and this table already holds both. Verified cell for cell against a directly built exact-run table at every size the slider offers. At the bottom of the 8-tile table those differences read 3888, 1332 and 456 for j = 1, 2 and 3, and they add back to the 5676 in the last column, which is the fold this page pushed into the state read straight back out. It is the same relationship nth-row-of-pascals-triangle has with binomial-coefficient, one cell against a whole row of the same table, with the direction reversed: there the row is the harder question, here the row is what the single cell was already summing.
Return the count modulo a prime p, the usual competitive-programming form.
The recurrence does not change: still m - 1 times the last column of the row above, plus the neighbour one column left. Only the write changes, taking a % p after the addition, which keeps every cell below p and removes the overflow question. That question is real here rather than notional, because the count grows by a factor tending to roughly 2.92 per tile: 3, 9, 27, 78, 228, 666, 1944 and 5676 at 1 to 8 tiles, and 48384 by 10. Shape, bases, fill order and dependency arrows are all untouched, and there is no division anywhere to need a modular inverse, which makes this the cheapest variation on the page.

Word Break Problem Box-Stacking Problem