Décoder des façons et compter des chemins
Résolvez decode-ways (correspondances chiffre-lettre) avec une DP similaire à celle de Fibonacci, puis comptez les chemins dans un escalier aux pas de taille variable.
Décoder des façons et compter des chemins est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Le problème du décodage
Décodage (LeetCode 91) associe une chaîne de chiffres à des lettres : 'A'=1, 'B'=2, ..., 'Z'=26. Étant donné une chaîne de chiffres codée, comptez le nombre de façons distinctes de la décoder. Par exemple, '12' peut être décodée comme 'AB' (1+2) ou 'L' (12), ce qui donne 2 façons. '226' peut donner 'BZ' (2+26), 'VF' (22+6) ou 'BBF' (2+2+6), ce qui donne 3 façons. Les zéros initiaux rendent certains décodages invalides.
# 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: 3Formulation DP pour les façons de décoder
Soit dp[i] = le nombre de façons de décoder s[:i]. Cas de base : dp[0] = 1 (chaîne vide, une seule façon) et dp[1] = 1 si s[0] != '0', sinon 0. Transition : si s[i-1] != '0', ajoutez dp[i-1] (décodage à un chiffre). Si 10 ≤ int(s[i-2:i]) ≤ 26, ajoutez dp[i-2] (décodage à deux chiffres). Il s’agit essentiellement du schéma de Fibonacci avec des vérifications de 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')) # 0Le piège du zéro initial
La partie la plus délicate des façons de décoder consiste à gérer les zéros. Un « 0 » isolé ne peut pas être décodé (aucune lettre ne correspond à 0) ; si s[i-1] == '0', n’ajoutez donc pas dp[i-1]. Un « 0 » en deuxième position n’est valide que si le nombre à deux chiffres vaut 10 ou 20. « 30 » ou « 40 » (et les nombres supérieurs) sont invalides, car ils dépassent 26. Vérifiez toujours 10 ≤ two_digit ≤ 26, et pas seulement 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)Façons de décoder avec optimisation de l’espace
Comme pour Fibonacci, la récurrence du nombre de décodages ne consulte que les deux positions précédentes ; vous pouvez donc réduire l’espace de O(n) à O(1) à l’aide de deux variables. Utilisez prev2 (deux étapes en arrière) et prev1 (une étape en arrière). À chaque étape, calculez curr à partir des deux précédentes, puis décalez-les. Il s’agit exactement de l’optimisation de Fibonacci à deux variables.
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')) # 0Compter les chemins dans un escalier
Monter les escaliers (LeetCode 70) pose la question suivante : de combien de façons pouvez-vous monter n marches si vous pouvez avancer de 1 ou 2 marches à la fois ? C’est exactement la suite de Fibonacci : ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Le problème se généralise lorsque vous pouvez avancer d’au plus k marches : 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!Monter les escaliers avec un nombre de marches variable
Lorsque vous pouvez avancer d’un nombre quelconque de marches appartenant à un ensemble donné (par exemple, {1, 3, 5}), la récurrence devient dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Utilisez une fenêtre glissante de taille max(steps) pour économiser de la mémoire. Il s’agit de la variante de comptage du problème du sac à dos non borné : chaque taille de pas peut être utilisée autant de fois que nécessaire.
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...)Monter les escaliers à coût minimal
Escalier à coût minimal (LeetCode 746) associe un coût à chaque marche et demande le coût minimal pour atteindre le sommet. Depuis la marche i, vous pouvez sauter à i+1 ou à i+2. La récurrence est dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Vous pouvez commencer à la marche 0 ou à la marche 1. La réponse est 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])) # 6Façons de décoder II : chiffre joker
Façons de décoder II (LeetCode 639) introduit le caractère joker « * », qui peut représenter n’importe quel chiffre de 1 à 9. Cela augmente considérablement le nombre de décodages valides. Un « * » seul contribue à 9 façons (pour chacun des chiffres de 1 à 9). Deux « * » ensemble peuvent former 9×9 combinaisons à deux chiffres, mais seules celles qui sont inférieures ou égales à 26 sont valides (11 à 19 = 9 façons, 21 à 26 = 6 façons, soit 15 façons pour « ** »). Une analyse attentive des différents cas est nécessaire.
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*')) # 18Le lien avec Fibonacci
Les problèmes des façons de décoder et de la montée des escaliers sont en réalité des problèmes de la famille de Fibonacci. Toute DP dans laquelle dp[i] dépend uniquement de dp[i-1] et de dp[i-2] suit une forme de Fibonacci et peut être résolue avec un espace O(1). Les vérifications de validité (chiffres zéro, tailles de pas) modifient les transitions actives, mais pas la structure fondamentale fondée sur les deux positions précédentes. Reconnaître immédiatement cette famille constitue un schéma précieux pour gagner du temps lors des entretiens.
# 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) # 89Compter les chemins dans une grille
Voici un problème de comptage associé : dans une grille m×n, combien de chemins uniques vont du coin supérieur gauche au coin inférieur droit si vous pouvez uniquement vous déplacer vers la droite ou vers le bas ? La réponse est le coefficient binomial C(m+n-2, m-1). La solution DP remplit un tableau 2D où dp[i][j] = dp[i-1][j] + dp[i][j-1]. Il s’agit d’une version 2D de l’escalier de Fibonacci : chaque cellule est la somme de la cellule située au-dessus et de celle située à gauche.
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)) # 6Résumé des pièges en entretien
Pièges fréquents dans les façons de décoder : (1) oublier que « 0 » seul est invalide — vérifiez toujours s[i-1] != '0' avant d’ajouter dp[i-1] ; (2) utiliser two_digit <= 26 sans vérifier two_digit >= 10 — « 07 » ne doit pas être décodé comme « G » ; (3) renvoyer dp[n-1] au lieu de dp[n] — le tableau est indexé à partir de 1, donc dp[n] correspond à la chaîne complète. Vérifiez toujours soigneusement les indices du tableau lorsque votre tableau DP contient un élément de plus que l’entrée.
# 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)Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : les façons de décoder suivent une récurrence semblable à celle de Fibonacci, avec des conditions de validité pour les décodages à un chiffre (non nul) et à deux chiffres (10 à 26) ; la montée des escaliers et l’escalier à coût minimal sont de simples variantes de Fibonacci, résolubles avec un espace O(1) ; et reconnaître la famille de Fibonacci fondée sur les deux positions précédentes permet de gagner beaucoup de temps lors des entretiens. Nous allons maintenant étudier la DP 2D avec les chemins uniques et la somme minimale d’un chemin dans des grilles.
Questions Fréquemment Posées
La leçon « Décoder des façons et compter des chemins » est-elle gratuite ?
Oui — le texte complet de « Décoder des façons et compter des chemins » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Décoder des façons et compter des chemins » ?
Résolvez decode-ways (correspondances chiffre-lettre) avec une DP similaire à celle de Fibonacci, puis comptez les chemins dans un escalier aux pas de taille variable. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Décoder des façons et compter des chemins » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- House Robber : récurrence prendre ou ignorer
- Sous-tableau de somme maximale et sous-tableau de produit maximal
- Word Break et segmentation de chaînes
- Décoder des façons et compter des chemins