Programmation dynamique

La différence majeure réside dans le chevauchement des sous-problèmes. Dans "Diviser pour régner" (ex: Tri fusion), les sous-problèmes sont indépendants. En programmation dynamique, les sous-problèmes se répètent. La PD utilise la mémoire pour éviter de recalculer ces répétitions.

💡 À retenir : Si les sous-problèmes sont indépendants, utilisez "Diviser pour régner". S'ils se chevauchent, utilisez la programmation dynamique.

L'algorithme glouton (Greedy) fait des choix locaux optimaux à chaque étape sans revenir en arrière. Si ces choix locaux ne mènent pas à une solution globale optimale, alors le problème nécessite la programmation dynamique, qui explore toutes les combinaisons possibles de manière efficace.

💡 À retenir : Si le choix glouton ne fonctionne pas, il faut envisager la programmation dynamique.

Oui, en termes de temps d'exécution (complexité temporelle), car elle réduit le nombre de calculs exponentiels en calculs polynomiaux. Cependant, elle consomme plus de mémoire (complexité spatiale) pour stocker les résultats intermédiaires.

💡 À retenir : C'est un compromis temps-mémoire (Space-Time Tradeoff).

L'état est l'ensemble des paramètres qui définissent de manière unique un sous-problème. Par exemple, dans le problème du sac à dos, l'état est (i, w) où i est l'indice de l'objet et w est le poids restant.

💡 À retenir : Bien définir l'état est la clé pour écrire la relation de récurrence.

La complexité spatiale est déterminée par la taille de la structure de données (tableau) utilisée pour stocker les résultats. Si tu utilises un tableau à deux dimensions de taille $N \times M$, la complexité est $O(N \times M)$.

💡 À retenir : Identifie la dimension de ton tableau de stockage.

Oui, toute solution récursive peut être transformée en une solution itérative (Bottom-Up) en utilisant une pile ou en remplissant un tableau dans l'ordre inverse de la récursion.

💡 À retenir : L'approche itérative est souvent préférée pour éviter les débordements de pile (Stack Overflow).

On utilise $n+1$ pour inclure le cas de base (souvent l'indice 0 ou 1) et pour que l'indice $n$ soit accessible directement dans le tableau.

💡 À retenir : Toujours vérifier les bornes de ton tableau pour éviter les erreurs d'index hors limites.

Oui, par exemple pour trouver le plus court chemin dans un graphe orienté acyclique (DAG) ou pour l'algorithme de Floyd-Warshall.

💡 À retenir : La PD est un outil puissant pour les problèmes de chemins optimaux.

Principalement oui, pour minimiser ou maximiser une valeur. Mais elle peut aussi servir à compter le nombre de façons d'atteindre un état (ex: nombre de chemins possibles).

💡 À retenir : L'optimisation est le cas d'usage classique, mais le dénombrement est aussi possible.

La mémoïsation est plus intuitive si tu connais déjà la solution récursive. La tabulation est souvent plus performante car elle évite la surcharge des appels de fonctions récursives.

💡 À retenir : La tabulation est généralement préférée en production pour sa stabilité.

Le programme se concentre sur les structures linéaires et les graphes. La PD sur les arbres est une extension, mais les principes de base (sous-problèmes) restent les mêmes.

💡 À retenir : Maîtrise d'abord la PD sur les tableaux avant d'aborder les arbres.

Oui, si le calcul d'un état ne dépend que de l'état précédent (ex: $T[i]$ dépend seulement de $T[i-1]$), on peut utiliser seulement deux variables au lieu d'un tableau complet.

💡 À retenir : C'est l'optimisation spatiale, très appréciée lors des examens.