Fence / tiling recurrences — painting the fence, friends pairing, cut segments, keypad, coin game, score-ways, ways to reach a score
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
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];}