Easy Problemscountinglinearcombinatorics

Painting Fence Algorithm

Given n fence posts and k available colors, count the number of ways to paint every post so that at most two consecutive posts ever share the same color.

Do this lesson first: climbing stairs

Example input

n = 6, k = 3

Expected output

492

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] = (k - 1) × (dp[i - 1] + dp[i - 2])

Ask what the last two posts could look like, not just the last one. Every valid painting of the first i posts either repeats post i-1's color once more, stretching a run to exactly two (there are dp[i-1] valid prefixes to extend this way, each extendable in k-1 further colors so the run never reaches three), or changes color entirely at post i (there are dp[i-2] valid prefixes of length i-2 to extend, again in k-1 ways, regardless of what closed each one off). Both cases scale by the same k-1, so they factor out as one multiplication over a sum rather than two separate additions.

dp[0] = 1 is the vacuous case: an empty prefix has exactly one arrangement, and it is a real value, not a placeholder. But unlike dp[1] and dp[2], dp[0] is never read by any later cell: with three bases in place the first compute cell is i = 3, and it reads only dp[2] and dp[1]. dp[0] fills the table's leftmost slot because every index needs a value, not because the recurrence reaches back that far. dp[1] = k and dp[2] = k² earn their place for a genuinely combinatorial reason instead: the general transition only starts holding once a run of three is even possible, and at i = 2 every pair of colors is still allowed, so dp[2] is the full k² rather than the (k-1)-scaled value the formula would wrongly give (for k = 3, that would be (k-1)(dp[1]+dp[0]) = 2 × 4 = 8, not the true 9). Every cell from i = 3 on depends only on smaller indices, so filling left to right guarantees both real dependencies exist before they are read.

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] = 1 is the vacuous case: an empty prefix has exactly one arrangement, and it is a real value, not a placeholder. But unlike dp[1] and dp[2], dp[0] is never read by any later cell: with three bases in place the first compute cell is i = 3, and it reads only dp[2] and dp[1]. dp[0] fills the table's leftmost slot because every index needs a value, not because the recurrence reaches back that far. dp[1] = k and dp[2] = k² earn their place for a genuinely combinatorial reason instead: the general transition only starts holding once a run of three is even possible, and at i = 2 every pair of colors is still allowed, so dp[2] is the full k² rather than the (k-1)-scaled value the formula would wrongly give (for k = 3, that would be (k-1)(dp[1]+dp[0]) = 2 × 4 = 8, not the true 9). Every cell from i = 3 on depends only on smaller indices, so filling left to right guarantees both real dependencies exist before they are read.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

1

3

9

24

66

180

492

painting-fence.ts

1function numWays(n, k) {
2 const dp = [1, k, k * k];
3 for (let i = 3; i <= n; i++) {
4 dp[i] = (k - 1) * (dp[i - 1] + dp[i - 2]);
5 }
6 return dp[n];
7}

Base caseComputedBeing readAnswer

The code, the trap, the variations

painting-fence.ts

1function numWays(n, k) {
2 const dp = [1, k, k * k];
3 for (let i = 3; i <= n; i++) {
4 dp[i] = (k - 1) * (dp[i - 1] + dp[i - 2]);
5 }
6 return dp[n];
7}

Where people go wrong

Reading the constraint as 'no two consecutive posts share a color' instead of the real rule: only three consecutive posts of the same color are forbidden, so up to two in a row are fine. Post i is allowed to match post i-1's color; it just cannot also match post i-2's, or a run of three forms. Solving the stricter no-two-alike version gives a different, smaller count from post 3 onward.

Forbid any two consecutive posts from sharing a color, not just three in a row.
The recurrence loses a term: dp[i] = (k - 1) × dp[i - 1], one dependency instead of two, since every post now only needs to differ from its immediate predecessor.
Allow up to three consecutive posts of the same color (forbid a run of four).
A third dependency joins the sum, dp[i] = (k - 1) × (dp[i-1] + dp[i-2] + dp[i-3]), with a fourth base case; the left-to-right order and the vacuous dp[0] = 1 stay the same.

Coin Change – Minimum Coins to Make Sum Cutting a Rod