Decode Ways i zliczanie ścieżek
Rozwiążą Państwo zadanie decode-ways — mapowanie cyfr na litery — jako DP podobne do ciągu Fibonacciego, a następnie policzą ścieżki na schodach o zmiennej liczbie kroków.
Decode Ways i zliczanie ścieżek to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem Decode Ways
Decode Ways (LeetCode 91) mapuje ciąg cyfr na litery: 'A'=1, 'B'=2, ..., 'Z'=26. Dla zakodowanego ciągu cyfr należy obliczyć liczbę różnych sposobów jego zdekodowania. Na przykład '12' można zdekodować jako 'AB' (1+2) lub 'L' (12), co daje 2 sposoby. '226' może oznaczać 'BZ' (2+26), 'VF' (22+6) lub 'BBF' (2+2+6), co daje 3 sposoby. Początkowe zera sprawiają, że niektóre dekodowania są niepoprawne.
# 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: 3Sformułowanie DP dla Decode Ways
Niech dp[i] oznacza liczbę sposobów dekodowania s[:i]. Przypadki bazowe: dp[0] = 1 (pusty ciąg, jeden sposób) oraz dp[1] = 1, jeśli s[0] != '0', w przeciwnym razie 0. Przejście: jeśli s[i-1] != '0', należy dodać dp[i-1] (dekodowanie jako pojedynczej cyfry). Jeśli 10 ≤ int(s[i-2:i]) ≤ 26, należy dodać dp[i-2] (dekodowanie jako dwóch cyfr). Jest to zasadniczo schemat Fibonacciego z kontrolą poprawności.
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')) # 0Pułapka wiodącego zera
Najtrudniejszą częścią problemu Decode Ways jest obsługa zer. Samodzielnego '0' nie można zdekodować (żadna litera nie odpowiada wartości 0), dlatego jeśli s[i-1] == '0', nie należy dodawać dp[i-1]. '0' jako druga cyfra jest poprawne tylko wtedy, gdy liczba dwucyfrowa wynosi 10 lub 20. '30' lub '40' (a także większe liczby) są niepoprawne, ponieważ przekraczają 26. Należy zawsze sprawdzać 10 ≤ two_digit ≤ 26, a nie tylko 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)Optymalizacja pamięci w Decode Ways
Podobnie jak w przypadku Fibonacciego, rekurencja liczby sposobów dekodowania odwołuje się tylko do dwóch poprzednich pozycji, więc pamięć O(n) można zmniejszyć do O(1)prev2 (wartość sprzed dwóch kroków) oraz prev1 (wartość sprzed jednego kroku). Przy każdym kroku należy obliczyć curr na podstawie obu wartości, a następnie je przesunąć. Jest to identyczna optymalizacja jak w przypadku Fibonacciego → dwóch zmiennych.
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')) # 0Zliczanie ścieżek na schodach
Climbing Stairs (LeetCode 70) pyta: na ile sposobów można wejść po n schodach, jeśli za każdym razem można pokonać 1 lub 2 stopnie? Jest to dokładnie ciąg Fibonacciego: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Rozwiązanie uogólnia się na przypadek, w którym można pokonać do k stopni: 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!Wchodzenie po schodach ze zmiennymi krokami
Gdy można pokonać dowolną liczbę stopni z danego zbioru (np. {1, 3, 5}), rekurencja przyjmuje postać dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Dla efektywnego wykorzystania pamięci należy użyć okna przesuwnego o rozmiarze max(steps). Jest to wariant zliczania problemu nieograniczonego plecaka — każdego rozmiaru kroku można użyć dowolną liczbę razy.
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...)Minimalny koszt wchodzenia po schodach
Min Cost Climbing Stairs (LeetCode 746) przypisuje koszt każdemu stopniowi i pyta o minimalny koszt dotarcia na szczyt. Ze stopnia i można przejść do i+1 lub i+2. Rekurencja ma postać dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Można rozpocząć od stopnia 0 lub stopnia 1. Odpowiedzią jest 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])) # 6Decode Ways II: cyfra wieloznaczna
Decode Ways II (LeetCode 639) wprowadza znak wieloznaczny '*' mogący reprezentować dowolną cyfrę od 1 do 9. Znacznie zwiększa to liczbę poprawnych dekodowań. Pojedyncza '*' daje 9 sposobów (po jednym dla każdej cyfry od 1 do 9). Dwie '*' mogą razem utworzyć 9×9 kombinacji dwucyfrowych, ale poprawne są tylko te ≤ 26 (11–19 = 9 sposobów, 21–26 = 6 sposobów → 15 sposobów dla '**'). Wymagana jest staranna analiza przypadków.
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*')) # 18Związek z ciągiem Fibonacciego
Zarówno Decode Ways, jak i Climbing Stairs to w istocie problemy z rodziny Fibonacciego. Każdy problem DP, w którym dp[i] zależy tylko od dp[i-1] i dp[i-2], ma strukturę Fibonacciego i można go rozwiązać przy użyciu pamięci O(1). Kontrole poprawności (cyfry zerowe, rozmiary kroków) zmieniają to, które przejścia są aktywne, ale nie zmieniają podstawowej struktury odwołań do dwóch poprzednich pozycji. Rozpoznawanie tej rodziny na pierwszy rzut oka to cenna umiejętność pozwalająca szybciej rozwiązywać zadania podczas rozmów kwalifikacyjnych.
# 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) # 89Zliczanie ścieżek w siatce
Pokrewny problem zliczania: dana jest siatka m×n; ile unikalnych ścieżek prowadzi z lewego górnego do prawego dolnego rogu, jeśli można poruszać się tylko w prawo lub w dół? Odpowiedzią jest współczynnik dwumianowy C(m+n-2, m-1). Rozwiązanie DP wypełnia tabelę 2D, w której dp[i][j] = dp[i-1][j] + dp[i][j-1]. Jest to dwuwymiarowa wersja schodów Fibonacciego — każda komórka jest sumą komórki powyżej i komórki po lewej.
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)) # 6Podsumowanie typowych pułapek na rozmowie kwalifikacyjnej
Typowe pułapki w problemie Decode Ways: (1) Zapomnienie, że samodzielne '0' jest niepoprawne — przed dodaniem dp[i-1] należy zawsze sprawdzić s[i-1] != '0'. (2) Użycie two_digit <= 26 bez sprawdzenia two_digit >= 10 — '07' nie powinno być dekodowane jako 'G'. (3) Zwrócenie dp[n-1] zamiast dp[n] — tabela jest indeksowana od 1, więc dp[n] odpowiada całemu ciągowi. Należy zawsze dokładnie sprawdzać indeksy tablicy, gdy tabela DP ma o jeden element więcej niż dane wejściowe.
# 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)Szybki test
Sprawdź swoją wiedzę na temat zagadnień Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: Decode Ways wykorzystuje rekurencję podobną do rekurencji Fibonacciego, z warunkami poprawności dla dekodowania pojedynczej cyfry (niezerowej) i dwóch cyfr (10–26), Climbing Stairs i Min Cost Staircase to czyste warianty Fibonacciego, które można rozwiązać przy użyciu pamięci O(1) oraz rozpoznanie rodziny Fibonacciego odwołującej się do dwóch poprzednich pozycji pozwala znacznie zaoszczędzić czas podczas rozmów kwalifikacyjnych. Następnie omówimy DP 2D na przykładzie Unique Paths i Minimum Path Sum dla siatek.
Często zadawane pytania
Czy lekcja „Decode Ways i zliczanie ścieżek” jest bezpłatna?
Tak — pełny tekst „Decode Ways i zliczanie ścieżek” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Decode Ways i zliczanie ścieżek”?
Rozwiążą Państwo zadanie decode-ways — mapowanie cyfr na litery — jako DP podobne do ciągu Fibonacciego, a następnie policzą ścieżki na schodach o zmiennej liczbie kroków. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Decode Ways i zliczanie ścieżek”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- House Robber: rekurencja wybierz albo pomiń
- Maksymalna podtablica i podtablica o maksymalnym iloczynie
- Word Break i dzielenie ciągu na segmenty
- Decode Ways i zliczanie ścieżek