Chemins dans une Grille
Programmation dynamique 2D — comptage de chemins
Enonce
Écrire nombre_chemins(m, n) qui renvoie le nombre de chemins distincts de (0, 0) à (m-1, n-1) dans une grille $m \times n$, en se déplaçant uniquement vers le bas ou vers la droite.
⚠ Contrainte : utiliser la programmation dynamique (pas de récursion naïve, qui serait exponentielle). Complexité visée $O(mn)$ temps.
Signature attendue
def nombre_chemins(m: int, n: int) -> int:Exemples
nombre_chemins(1, 1)→1 (une seule case)nombre_chemins(2, 2)→2 (droite-bas ou bas-droite)nombre_chemins(3, 3)→6
📖 Rappel de cours
On considère une grille rectangulaire de $m$ lignes et $n$ colonnes. On part de la case (0, 0) et on veut atteindre (m-1, n-1) en se déplaçant uniquement d'une case vers la droite ou d'une case vers le bas. Combien de chemins distincts existe-t-il ?
Récurrence :
Notons $C(i, j)$ le nombre de chemins de $(0,0)$ à $(i,j)$.
- $C(0, j) = 1$ (une seule route : tout droit)
- $C(i, 0) = 1$ (une seule route : tout en bas)
- $C(i, j) = C(i-1, j) + C(i, j-1)$ pour $i, j \geq 1$
On reconnaît le triangle de Pascal : $C(i, j) = \binom{i+j}{i}$. Mais programmer la récurrence directement est plus pédagogique et se généralise à des obstacles.
Complexité $O(mn)$ temps et espace pour le tableau. Espace réductible à $O(\min(m,n))$ en ne gardant qu'une ligne.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Arbre Binaire de Recherche (ABR)
- Tri par Tas (Heap Sort)
- Algorithme de Kadane
- Distance d'Édition (Levenshtein)
- Rendu de Monnaie (DP)
- Problème des N-Reines
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.