Decode Ways en paden tellen
Los decode-ways (cijfer-naar-letterkoppelingen) op als Fibonacci-achtige DP en tel vervolgens paden in een trap met variabele stapgroottes.
Decode Ways en paden tellen is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Het probleem van het decoderen
Decoderen (LeetCode 91) koppelt een tekenreeks met cijfers aan letters: 'A'=1, 'B'=2, ..., 'Z'=26. Gegeven een gecodeerde cijferreeks tel je het aantal verschillende manieren om die te decoderen. Zo kan '12' worden gedecodeerd als 'AB' (1+2) of als 'L' (12), wat 2 manieren oplevert. '226' kan 'BZ' (2+26), 'VF' (22+6) of 'BBF' (2+2+6) zijn, wat 3 manieren oplevert. Voorloopnullen maken sommige decoderingen ongeldig.
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3DP-formulering voor decodeerwijzen
Stel dp[i] = het aantal manieren om s[:i] te decoderen. Basisgevallen: dp[0] = 1 (lege tekenreeks, één manier) en dp[1] = 1 als s[0] != '0', anders 0. Overgang: als s[i-1] != '0', tel je dp[i-1] erbij op (decodering met één cijfer). Als 10 ≤ int(s[i-2:i]) ≤ 26, tel je dp[i-2] erbij op (decodering met twee cijfers). Dit is in wezen het Fibonacci-patroon met geldigheidscontroles.
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0De valkuil van voorloopnullen
Het lastigste onderdeel van decodeerwijzen is het verwerken van nullen. Een losse '0' kan niet worden gedecodeerd (geen enkele letter correspondeert met 0), dus als s[i-1] == '0', tel je dp[i-1] niet erbij op. Een '0' als tweede cijfer is alleen geldig als het tweecijferige getal 10 of 20 is. '30' of '40' (en hogere getallen) zijn ongeldig, omdat ze groter zijn dan 26. Controleer altijd 10 ≤ two_digit ≤ 26, en niet alleen two_digit ≤ 26.
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)Decodeerwijzen met geoptimaliseerd geheugengebruik
Net als bij Fibonacci kijkt de recurrentie voor het aantal decodeerwijzen slechts twee posities terug, dus je kunt de geheugenruimte van O(n) terugbrengen naar O(1) met twee variabelen. Gebruik prev2 (twee stappen terug) en prev1 (één stap terug). Bereken bij elke stap curr op basis van beide waarden en verschuif ze vervolgens. Dit is dezelfde optimalisatie met twee variabelen als bij Fibonacci.
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0Paden tellen op een trap
Trappen beklimmen (LeetCode 70) vraagt: op hoeveel manieren kun je n traptreden beklimmen als je telkens 1 of 2 treden mag nemen? Dit is precies de Fibonacci-reeks: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Je kunt dit uitbreiden naar situaties waarin je maximaal k treden mag nemen: ways(n) = sum(ways(n-1), ..., ways(n-k)).
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!Trappen beklimmen met variabele stapgroottes
Als je een willekeurig aantal stappen uit een bepaalde verzameling mag nemen (bijvoorbeeld {1, 3, 5}), wordt de recurrentie dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Gebruik voor efficiënt geheugengebruik een schuivend venster met de grootte max(steps). Dit is de telvariant van het onbegrensde-rugzakprobleem — elke stapgrootte kan een onbeperkt aantal keer worden gebruikt.
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)Trappen beklimmen met minimale kosten
Trappen beklimmen met minimale kosten (LeetCode 746) koppelt aan elke trede een kost en vraagt naar de minimale kost om de top te bereiken. Vanaf trede i kun je naar i+1 of i+2 springen. De recurrentie is dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Je kunt beginnen bij trede 0 of trede 1. Het antwoord is min(dp[n-1], dp[n-2]).
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6Decodeerwijzen II: jokercijfer
Decodeerwijzen II (LeetCode 639) introduceert het jokerteken '*' dat elk cijfer van 1 tot en met 9 kan voorstellen. Hierdoor neemt het aantal geldige decoderingen sterk toe. Een enkele '*' levert 9 manieren op (voor elk cijfer van 1 tot en met 9). Twee '*' samen kunnen 9×9 tweecijferige combinaties vormen, maar alleen de combinaties ≤ 26 zijn geldig (11-19 = 9 manieren, 21-26 = 6 manieren → 15 manieren voor '**'). Een zorgvuldige gevalsanalyse is vereist.
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18Het verband met Fibonacci
Zowel decodeerwijzen als trappen beklimmen zijn vermomde problemen uit de Fibonacci-familie. Elke DP waarbij dp[i] alleen afhangt van dp[i-1] en dp[i-2], heeft de vorm van Fibonacci en kan met O(1) geheugenruimte worden opgelost. De geldigheidscontroles (nulcijfers, stapgroottes) bepalen welke overgangen actief zijn, maar veranderen niet de fundamentele structuur waarbij je twee posities terugkijkt. Als je deze familie direct herkent, levert dat tijdens technische sollicitatiegesprekken waardevolle tijdwinst op.
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89Paden tellen op een rooster
Een verwant telprobleem: gegeven een rooster van m×n, op hoeveel unieke manieren kun je van de linkerbovenhoek naar de rechterbenedenhoek gaan als je alleen naar rechts of naar beneden mag bewegen? Het antwoord is de binomiaalcoëfficiënt C(m+n-2, m-1). De DP-oplossing vult een tweedimensionale tabel in waarin dp[i][j] = dp[i-1][j] + dp[i][j-1]. Dit is een tweedimensionale versie van de Fibonacci-trap — elke cel is de som van de cel erboven en de cel links ervan.
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6Samenvatting van valkuilen bij sollicitatiegesprekken
Veelvoorkomende valkuilen bij decodeerwijzen: (1) vergeten dat '0' op zichzelf ongeldig is — controleer altijd s[i-1] != '0' voordat je dp[i-1] erbij optelt. (2) two_digit <= 26 gebruiken zonder two_digit >= 10 te controleren — '07' mag niet als 'G' worden gedecodeerd. (3) dp[n-1] teruggeven in plaats van dp[n] — de tabel is 1-geïndexeerd, dus dp[n] correspondeert met de volledige tekenreeks. Controleer array-indexen altijd extra goed wanneer je DP-tabel één element meer bevat dan de invoer.
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)Snelle controle
Test je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep die in deze les aan bod kwamen.
Samenvatting van de les
In deze les heb je geleerd: decodeerwijzen volgt een op Fibonacci lijkende recurrentie met geldigheidsvoorwaarden voor decoderingen van één cijfer (niet nul) en twee cijfers (10-26), trappen beklimmen en trappen beklimmen met minimale kosten zijn zuivere Fibonacci-varianten die met O(1) geheugenruimte kunnen worden opgelost, en het herkennen van de Fibonacci-familie waarbij je twee posities terugkijkt, bespaart aanzienlijk veel tijd tijdens sollicitatiegesprekken. Hierna verkennen we tweedimensionale DP met Unieke paden en Minimale padsom op roosters.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Decode Ways en paden tellen” gratis?
Ja — de volledige tekst van “Decode Ways en paden tellen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Decode Ways en paden tellen”?
Los decode-ways (cijfer-naar-letterkoppelingen) op als Fibonacci-achtige DP en tel vervolgens paden in een trap met variabele stapgroottes. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Decode Ways en paden tellen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- House Robber: recurrentie voor nemen of overslaan
- Maximumsubarray en maximumproductsubarray
- Word Break en strings segmenteren
- Decode Ways en paden tellen