Decode Ways e conteggio dei percorsi
Risolva decode-ways (corrispondenze cifra-lettera) come una DP simile a Fibonacci, poi conti i percorsi su una scala con passi di dimensione variabile
Decode Ways e conteggio dei percorsi è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Il problema Decode Ways
Decode Ways (LeetCode 91) associa una stringa di cifre alle lettere: 'A'=1, 'B'=2, ..., 'Z'=26. Data una stringa di cifre codificata, occorre contare il numero di modi distinti per decodificarla. Ad esempio, '12' può essere decodificata come 'AB' (1+2) oppure 'L' (12), per un totale di 2 modi. '226' può diventare 'BZ' (2+26), 'VF' (22+6) oppure 'BBF' (2+2+6), per un totale di 3 modi. Gli zeri iniziali rendono non valide alcune decodifiche.
# 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: 3Formulazione DP per Decode Ways
Sia dp[i] il numero di modi per decodificare s[:i]. Casi base: dp[0] = 1 (stringa vuota, un solo modo) e dp[1] = 1 se s[0] != '0', altrimenti 0. Transizione: se s[i-1] != '0', si aggiunge dp[i-1] (decodifica di una singola cifra). Se 10 ≤ int(s[i-2:i]) ≤ 26, si aggiunge dp[i-2] (decodifica di due cifre). Si tratta essenzialmente dello schema di Fibonacci con controlli di validità.
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')) # 0La trappola dello zero iniziale
La parte più delicata di Decode Ways consiste nella gestione degli zeri. Uno '0' isolato non può essere decodificato (nessuna lettera corrisponde a 0), quindi, se s[i-1] == '0', non si deve aggiungere dp[i-1]. Uno '0' come seconda cifra è valido solo se il numero a due cifre è 10 o 20. '30' o '40' (e tutti i numeri superiori) non sono validi perché superano 26. Si verifichi sempre 10 ≤ two_digit ≤ 26, non soltanto 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)Decode Ways con ottimizzazione dello spazio
Come per Fibonacci, la ricorrenza dei modi di decodifica considera solo le due posizioni precedenti, quindi è possibile ridurre lo spazio da O(n) a O(1) usando due variabili. Si usino prev2 (due passi indietro) e prev1 (un passo indietro). A ogni passo si calcoli curr a partire da entrambe, quindi le si facciano avanzare. Si tratta della stessa ottimizzazione di Fibonacci → a due variabili.
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')) # 0Conteggio dei percorsi su una scala
Climbing Stairs (LeetCode 70) chiede: in quanti modi si possono salire n gradini, potendo fare 1 o 2 gradini alla volta? Si tratta esattamente della successione di Fibonacci: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Il caso si generalizza quando si possono fare fino a k gradini: 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!Salire le scale con passi variabili
Quando è possibile fare un numero qualsiasi di passi appartenenti a un insieme dato (ad esempio, {1, 3, 5}), la ricorrenza diventa dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Per usare la memoria in modo efficiente, si utilizzi una finestra scorrevole di dimensione max(steps). Questa è la variante di conteggio dello zaino illimitato: ogni dimensione di passo può essere usata un numero qualsiasi di volte.
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...)Salita delle scale a costo minimo
Min Cost Climbing Stairs (LeetCode 746) assegna un costo a ogni gradino e chiede il costo minimo per raggiungere la cima. Dal gradino i si può saltare a i+1 o a i+2. La ricorrenza è dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Si può partire dal gradino 0 o dal gradino 1. La risposta è 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: cifra jolly
Decode Ways II (LeetCode 639) introduce il carattere jolly '*' che può rappresentare qualsiasi cifra da 1 a 9. Questo aumenta notevolmente il numero di decodifiche valide. Un singolo '*' contribuisce con 9 modi (come una qualsiasi cifra da 1 a 9). Due '*' insieme possono formare 9×9 combinazioni a due cifre, ma sono valide solo quelle ≤ 26 (11-19 = 9 modi, 21-26 = 6 modi → 15 modi per '**'). È necessaria un'attenta analisi dei casi.
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*')) # 18Collegamento con Fibonacci
Sia Decode Ways sia Climbing Stairs sono problemi della famiglia di Fibonacci camuffati. Qualsiasi problema di DP in cui dp[i] dipende solo da dp[i-1] e dp[i-2] segue lo schema di Fibonacci e può essere risolto usando spazio O(1). I controlli di validità (cifre zero, dimensioni dei passi) modificano quali transizioni sono attive, ma non la struttura fondamentale che considera le due posizioni precedenti. Riconoscere a colpo d'occhio questa famiglia è uno schema prezioso per essere rapidi nei colloqui.
# 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) # 89Conteggio dei percorsi su una griglia
Un problema di conteggio correlato è il seguente: data una griglia m×n, quanti percorsi distinti vanno dall'angolo in alto a sinistra a quello in basso a destra, se ci si può muovere solo a destra o verso il basso? La risposta è il coefficiente binomiale C(m+n-2, m-1). La soluzione DP riempie una tabella 2D in cui dp[i][j] = dp[i-1][j] + dp[i][j-1]. È una versione 2D della scala di Fibonacci: ogni cella è la somma della cella sopra e di quella a sinistra.
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)) # 6Riepilogo degli errori comuni nei colloqui
Errori comuni in Decode Ways: (1) dimenticare che '0' da solo non è valido: si verifichi sempre s[i-1] != '0' prima di aggiungere dp[i-1]. (2) Usare two_digit <= 26 senza verificare two_digit >= 10: '07' non deve essere decodificato come 'G'. (3) Restituire dp[n-1] invece di dp[n]: la tabella è indicizzata a partire da 1, quindi dp[n] corrisponde all'intera stringa. Si ricontrollino sempre gli indici degli array quando la tabella DP contiene un elemento in più rispetto all'input.
# 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)Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: Decode Ways segue una ricorrenza simile a quella di Fibonacci, con controlli di validità per le decodifiche a una cifra (diversa da zero) e a due cifre (10-26), Climbing Stairs e Min Cost Staircase sono varianti pure di Fibonacci risolvibili con spazio O(1) e riconoscere la famiglia di Fibonacci che considera le due posizioni precedenti fa risparmiare molto tempo durante i colloqui. Ora passeremo alla DP 2D con Unique Paths e Minimum Path Sum sulle griglie.
Domande Frequenti
La lezione «Decode Ways e conteggio dei percorsi» è gratuita?
Sì — il testo completo di «Decode Ways e conteggio dei percorsi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Decode Ways e conteggio dei percorsi»?
Risolva decode-ways (corrispondenze cifra-lettera) come una DP simile a Fibonacci, poi conti i percorsi su una scala con passi di dimensione variabile Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Decode Ways e conteggio dei percorsi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- House Robber: ricorrenza prendi o salta
- Subarray a somma massima e subarray a prodotto massimo
- Word Break e segmentazione delle stringhe
- Decode Ways e conteggio dei percorsi