Somme de chemin minimale
Étant donné une grille de hauteur h et de largeur w remplie d’entiers, votre objectif est de trouver un chemin allant du coin supérieur gauche au coin inférieur droit, de manière à minimiser la somme des nombres le long de ce chemin. Vous n’êtes autorisé qu’à vous déplacer vers la droite ou vers le bas.
3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Entrée
La première ligne de l’entrée contient deux entiers h et w (1 ≤ h, w ≤ 1000).
Les h lignes suivantes contiennent w entiers séparés par un espace, , représentant les valeurs dans la grille .
Sortie
Le programme doit afficher la somme minimale possible pour aller du coin supérieur gauche au coin inférieur droit.
Exemples
Entrée | Sortie |
|---|---|
3 4 3 2 1 3 1 9 2 3 9 1 5 4 | 15 |
Explication
On peut se déplacer ainsi : 3 → 2 → 1 → 2 → 3 → 4.
Hint 1
L’état dans un problème de programmation dynamique peut être un tableau à deux dimensions.
Hint 2
Il peut représenter la meilleure solution possible jusqu’à cette coordonnée (d[r][c] représente le meilleur chemin pour atteindre la ligne r et la colonne c).
Pourquoi l’approche gloutonne ne fonctionne-t-elle pas ici ? Imaginez que vous vous déplaciez toujours vers la plus petite valeur possible. Quel serait le problème dans ce cas ?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB