Somme minimale d’un chemin avec obstacles
Propager le meilleur coût à travers les cellules
Somme minimale d’un chemin avec obstacles est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Du comptage au coût
Désormais, chaque cellule contient une valeur et vous cherchez le trajet le moins coûteux jusqu'au coin. L'objectif passe du comptage des chemins à la minimisation d'un coût.
Définir l'état
Soit dp[i][j] le coût total minimal pour atteindre la cellule (i, j). Même grille, mêmes déplacements, mais vous suivez des sommes plutôt que des nombres de chemins.
La transition
Vous choisissez le moins cher des deux voisins entrants, puis ajoutez la valeur de la cellule actuelle. Ce choix du minimum est au cœur de la récurrence.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Marquer les obstacles
Un obstacle est une cellule sur laquelle vous ne pouvez pas vous placer. Donnez-lui un coût égal à l'infini afin qu'aucun chemin qui la traverse ne soit minimal.
INF = float('inf')Bloquer proprement la cellule
Lorsque la grille indique qu'une cellule est bloquée, affectez simplement l'infini à son dp et poursuivez. L'étape du minimum l'évitera naturellement.
if blocked(i, j):
dp[i][j] = INF
continueProtéger le départ
Si la cellule de départ est elle-même bloquée, aucun chemin n'existe. Vérifiez-le en premier afin de ne pas renvoyer un coût aberrant.
Initialiser la première cellule
La cellule de départ n'a aucun voisin d'où venir, son coût est donc simplement sa propre valeur. Affectez dp[0][0] avant le début des boucles.
dp[0][0] = grid[0][0]Gérer les bords
La première ligne ne progresse que depuis la gauche, et la première colonne uniquement depuis le dessus. Traitez ces bords pour ne jamais lire en dehors de la grille.
L'infini se propage
Ajouter une valeur à l'infini donne toujours l'infini, une cellule complètement isolée conserve donc son coût INF. Les cellules inaccessibles se signalent automatiquement.
Lire le résultat
Le coût minimal se trouve dans la cellule en bas à droite. Si cette valeur est encore infinie, aucun chemin valide n'existe.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1Quand l'approche gloutonne échoue
Toujours avancer vers le voisin dont la valeur est la plus petite peut vous piéger. Seul un DP complet garantit le chemin globalement le moins coûteux, et non un simple choix glouton.
Vérification rapide
Comment faire pour que le DP des chemins évite une cellule bloquée sans traiter séparément chaque voisin ?
Récapitulatif : chemin minimal avec obstacles
Prenez le voisin le moins cher, ajoutez la valeur de la cellule, affectez l'infini aux cellules bloquées, puis lisez le coin. La valeur INF à cet endroit signifie aucun chemin. 🧱
Questions Fréquemment Posées
La leçon « Somme minimale d’un chemin avec obstacles » est-elle gratuite ?
Oui — le texte complet de « Somme minimale d’un chemin avec obstacles » 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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Somme minimale d’un chemin avec obstacles » ?
Propager le meilleur coût à travers les cellules Tu pratiques Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 2 sur 4.
Combien de temps prend la leçon « Somme minimale d’un chemin avec obstacles » ?
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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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