Fence / tiling recurrences — painting the fence, friends pairing, cut segments, keypad, coin game, score-ways, ways to reach a score

Medium

Problem

Short 1-D recurrences:

Painting the fence — n posts and k colours, with no more than two adjacent posts the same colour. Friends pairing — each of n friends stays single or pairs with one other. Maximise cut segments — cut a length n into as many pieces of lengths x, y or z as possible. Mobile keypad — count the n-digit numbers where each next digit is the same key or an adjacent one. Ways to reach a score — using moves of 3, 5 and 10, counting combinations.

Example 1

Input:  fence n = 3, k = 2
Output: 6

Example 2

Input:  friends pairing n = 3
Output: 4

Also asked as: Painting the Fenceproblem · Friends Pairing Problem · Maximize The Cut Segments · Mobile Numeric Keypad Problem · Coin game winner where every player has three choices · Count number of ways to reacha given score in a game · Minimum cost to fill given weight in a bag

Test cases

Case 1

Input:    3, 2
Expected: 6

Case 2

Input:    4, 2
Expected: 10

Case 3

Input:    2, 4
Expected: 16

Case 4

Input:    1, 3
Expected: 3

Case 5

Input:    0, 2
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Linear recurrences

Time O(n)Space O(1)–O(n)

Painting the fence (k colours, no 3 adjacent same): total(i) = (same(i) + diff(i)); same(i) = diff(i−1); diff(i) = (total(i−1))·(k−1). Friends pairing: f(n) = f(n−1) + (n−1)·f(n−2). Cut segments (max pieces of size a/b/c from n): dp[i] = 1 + max(dp[i−a], dp[i−b], dp[i−c]). Ways to reach score with moves {3,5,10}: unbounded-coin-change count.

function paintFence(n, k) {
if (n === 0) return 0;
if (n === 1) return k;
let same = k, diff = k * (k - 1);
for (let i = 3; i <= n; i++) {
const prevDiff = diff;
diff = (same + diff) * (k - 1);
same = prevDiff;
}
return same + diff;
}
function friendsPairing(n) {
let a = 1, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, b + (i - 1) * a];
return b;
}
function maxCutSegments(n, a, b, c) {
const dp = new Array(n + 1).fill(-Infinity);
dp[0] = 0;
for (let i = 1; i <= n; i++)
for (const seg of [a, b, c])
if (i >= seg && dp[i - seg] !== -Infinity) dp[i] = Math.max(dp[i], dp[i - seg] + 1);
return dp[n] < 0 ? 0 : dp[n];
}