Compter les chemins sur une grille
Additionner les chemins d’un coin à l’autre
Compter les chemins sur une grille est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème classique de la grille
Vous commencez en haut à gauche d'une grille et voulez atteindre le coin inférieur droit. Chaque étape se fait vers la droite ou vers le bas. Combien de chemins distincts existe-t-il ?
Pourquoi le DP convient
Chaque cellule peut être atteinte depuis la cellule située au-dessus ou celle située à sa gauche. Ce chevauchement explique précisément pourquoi il s'agit d'un problème de DP.
Définir l'état
Soit dp[i][j] le nombre de façons d'atteindre la cellule (i, j) depuis le départ. Nommer clairement l'état représente déjà la moitié du travail.
La transition
Vous n'arrivez que d'en haut ou de la gauche, donc le nombre de chemins est leur somme. C'est la transition qui fait fonctionner tout le tableau.
dp[i][j] = dp[i-1][j] + dp[i][j-1]Le cas de base
Il n'existe qu'une seule façon d'atteindre la cellule de départ : ne rien faire. Ainsi, dp[0][0] vaut 1 avant de remplir le reste.
dp[0][0] = 1Un seul chemin sur les bords
Les cellules de la première ligne ou de la première colonne n'ont qu'un seul chemin direct. Leur nombre vaut toujours 1, car l'un de leurs voisins est hors de la grille.
Construire le tableau
Créez un tableau de m par n rempli de zéros. Le dimensionner dès le départ simplifie vos indices et évite les surprises.
dp = [[0] * n for _ in range(m)]Remplir dans l'ordre de lecture
Parcourez d'abord les lignes, puis les colonnes, de haut en bas et de gauche à droite. Cet ordre garantit que les deux voisins sont prêts avant leur utilisation.
for i in range(m):
for j in range(n):
...La cellule de la réponse
Une fois le tableau rempli, le nombre de chemins se trouve dans la dernière cellule. La réponse est dp[m-1][n-1], dans le coin inférieur droit.
answer = dp[m-1][n-1]Économiser la mémoire avec une seule ligne
Chaque ligne n'a besoin que de la ligne précédente, vous pouvez donc conserver une seule ligne et la mettre à jour sur place. La mémoire passe ainsi à O(n).
row[j] += row[j-1]L'astuce mathématique
Sans obstacles, la réponse est un coefficient binomial : choisissez quelles étapes, parmi toutes, descendent. Le DP reste préférable dès que des obstacles apparaissent.
Vérification rapide
Vous remplissez dp[i][j] pour une cellule intérieure libre. Quelle formule est correcte ?
Récapitulatif : comptage des chemins
Définissez dp comme le nombre de chemins vers une cellule, affectez 1 à dp[0][0], puis additionnez la cellule du dessus et celle de gauche. Le coin contient votre réponse. 🧭
Questions Fréquemment Posées
La leçon « Compter les chemins sur une grille » est-elle gratuite ?
Oui — le texte complet de « Compter les chemins sur une grille » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Compter les chemins sur une grille » ?
Additionner les chemins d’un coin à l’autre Tu pratiques Coding 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding 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 1 sur 4.
Combien de temps prend la leçon « Compter les chemins sur une grille » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding 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
- Compter les chemins sur une grille
- Somme minimale d’un chemin avec obstacles
- Plus longue sous-séquence commune
- Distance d’édition étape par étape