Programmation dynamique : cours, mémoïsation, sac à dos et exercices corrigés de prépa

Q: Quelle est la complexité du sac à dos en programmation dynamique ?

Avec n objets et une charge c, il y a (n + 1)(c + 1) sous-problèmes, chacun calculé en temps constant à partir de deux cases : O(nc) en temps et en mémoire, pour les deux versions. Comme une ligne ne dépend que de la précédente, deux lignes suffisent pour la valeur optimale, en O(c) de mémoire, mais la reconstruction est perdue. Ce coût dépend de la valeur de c, pas de sa longueur d'écriture : la même charge comptée en kilogrammes au lieu de quintaux passe de 15 à 1500 colonnes. Au programme marocain, le meilleur cas de la version mémoïsée, tous les objets trop lourds, fait n + 1 appels, en Θ (n).

MP
PC
PSI
PT
Offert à l'essai

Sous-structure optimale et chevauchement des sous-problèmes, équation de récurrence, mémoïsation et méthode ascendante, reconstruction d'une solution, sac à dos, rendu de monnaie, partition équilibrée, ordonnancement de tâches pondérées, plus longue sous-suite commune, distance d'édition, complexités en temps et en mémoire, comparaison avec les algorithmes gloutons, Floyd-Warshall (classes françaises).

19méthodes
36exercices corrigés
4problèmes
21pièges
50figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

La programmation dynamique résout un problème d'optimisation en le découpant en sous-problèmes du même type, chacun résolu une seule fois, dont les réponses sont gardées dans un tableau ou un dictionnaire. Elle demande deux propriétés : la sous-structure optimale, qui la rend exacte, et le chevauchement des sous-problèmes, qui la rend rapide. Le chapitre est au programme d'informatique commune de deuxième année en MP et PSI, au Maroc et en France, et en PC et PT en France. Il enseigne à définir le sous-problème par une phrase exacte, à écrire la récurrence avec ses cas de base et ses cas interdits, à programmer la version descendante par mémoïsation et la version ascendante par un tableau, à reconstruire une solution optimale et à justifier la complexité en temps et en mémoire. Les exemples sont le sac à dos binaire, où le glouton ne donne que 117 quand l'optimum vaut 132, le rendu de monnaie, la partition équilibrée, la plus longue sous-suite commune, la distance d'édition, le chemin de coût minimal dans une grille et les tâches pondérées ; les classes françaises y ajoutent l'algorithme de Floyd-Warshall, et le programme marocain demande le meilleur et le pire cas. Les exercices et les problèmes reprennent des questions des sujets du CNC, de Mines-Ponts, de X-ENS et de CCINP.

Ce que tu sauras faire

Beaucoup de problèmes d'optimisation se découpent en problèmes plus petits du même type. Quand ces petits problèmes reviennent sans cesse, les résoudre une seule fois et garder leurs réponses change tout : un calcul exponentiel devient un calcul de quelques milliers d'opérations. C'est l'idée de la programmation dynamique. Elle donne toujours l'optimum, au prix d'un tableau à remplir.

reconnaître les deux propriétés qui rendent la méthode possible et utile : sous-structure optimale et chevauchement des sous-problèmes ;
définir un sous-problème par une phrase exacte, puis écrire sa récurrence, ses cas de base et ses cas interdits ;
programmer les deux versions, descendante par mémoïsation et ascendante par un tableau, et dire ce qui les distingue ;
reconstruire une solution optimale à partir du tableau ;
justifier la complexité en temps et en mémoire ;
traiter les exemples classiques : sac à dos, rendu de monnaie, partition, plus longue sous-suite commune, distance d'édition, chemin dans une grille, tâches pondérées ;
comparer la programmation dynamique et la stratégie gloutonne.

L'essentiel : Le sac à dos binaire, modèle de tout le chapitre Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

$T[i][r]$ : meilleure valeur avec les $i$ premiers objets et une charge $r$ . L'objet $i - 1$ , de valeur $v$ et de poids $p$ , est laissé ou pris :

T[i][r] = \max\big(T[i-1][r],\ v + T[i-1][r-p]\big) \text{ si } p \le r, \qquad T[i][r] = T[i-1][r] \text{ sinon},

avec $T[0][r] = 0$ . Réponse : $T[n][c]$ .

def sac_memo(objets, i, r, memo):
    if (i, r) in memo:              # test en tête
        return memo[(i, r)]
    if i == 0:
        s = 0
    else:
        v, p = objets[i - 1]
        s = sac_memo(objets, i - 1, r, memo)
        if p <= r:                  # cas interdit exclu
            t = v + sac_memo(objets, i - 1, r - p, memo)
            if t > s:
                s = t
    memo[(i, r)] = s                # rangé avant le return
    return s

def sac_table(objets, c):
    n = len(objets)
    T = [[0] * (c + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        v, p = objets[i - 1]
        for r in range(c + 1):
            T[i][r] = T[i - 1][r]
            if p <= r and v + T[i - 1][r - p] > T[i][r]:
                T[i][r] = v + T[i - 1][r - p]
    return T

def sac_choix(objets, c, T):
    n = len(objets)
    pris = [False] * n
    r = c
    i = n
    while i > 0:                    # remontée
        if T[i][r] != T[i - 1][r]:  # objet i - 1 pris
            pris[i - 1] = True
            r = r - objets[i - 1][1]
        i = i - 1
    choix = []
    for j in range(n):
        if pris[j]:
            choix.append(j)
    return choix

La remontée coûte $O(n)$ : on marque les objets pris, puis on les relit dans l'ordre. Un ajout en tête, pris = [i - 1] + pris, recopierait la liste à chaque fois.

Appel : sac_memo(objets, len(objets), c, {}), avec un dictionnaire neuf. Sur les six lots du camion et 15 quintaux : 132, lots 1, 2 et 5 ; le glouton du rapport ne donne que 117.

Une méthode du chapitre Extrait gratuit

Méthode Comparer glouton et programmation dynamique sur un même problème

Quand l’utiliser

L'énoncé demande de comparer deux méthodes, de dire si un glouton est pertinent, ou de mettre en rapport la sous-structure optimale dans les deux stratégies.

Rappel de cours

Le glouton fait un seul choix par critère, sans retour ; il est rapide, mais n'est exact que si le choix glouton figure toujours dans une solution optimale. La programmation dynamique compare tous les choix ; elle est exacte dès que la sous-structure optimale est vraie, pour un coût plus élevé (cours, section 3.3).

Démarche

Écrire le critère du glouton et le dérouler sur un petit exemple.
Calculer l'optimum par programmation dynamique sur le même exemple.
Si les valeurs diffèrent, c'est un contre-exemple : le glouton n'est pas exact.
Comparer les coûts, avec toutes les tailles.
Conclure : vitesse contre garantie.

Rédaction type

« Le glouton est en $O(n \log n)$ , mais il ne garantit pas l'optimum : sur [entrée], il donne [valeur] alors que l'optimum vaut [valeur]. La programmation dynamique donne toujours l'optimum, en $O(\ldots)$ . Les deux reposent sur la sous-structure optimale ; le glouton exige en plus que son choix soit toujours le bon. »

Exemple traité

Lots alignés [5, 6, 5]. Le glouton qui prend le plus grand lot permis choisit 6, puis ne peut plus rien prendre : valeur 6. La programmation dynamique donne lots_alignes([5, 6, 5])[3] = 10, avec les lots 0 et 2. Le glouton coûte un tri, $O(n \log n)$ ; la programmation dynamique coûte $O(n)$ ici : le glouton n'est pas toujours le plus rapide.

Erreurs fréquentes

Dire qu'un glouton est toujours faux, ou que la programmation dynamique est toujours plus lente.
Prouver qu'un glouton est exact par quelques tests.
Oublier que la sous-structure optimale sert aux deux méthodes.

Pour s’entraîner

Exercices 1, 15, 20 et 21, problème 1.

Un exercice corrigé Extrait gratuit

Exercice Le sac du fret ★☆☆

On charge un conteneur : $n$ objets, chacun pris entier ou laissé, une quantité totale de ressources disponibles $b$ . Attention, le sujet écrit chaque objet sous la forme (r, p) : d'abord la ressource consommée $r_i$ (le poids), puis le profit $p_i$ (la valeur), soit l'ordre inverse du cours. On garde ici l'ordre du sujet. Pour $k$ de 0 à $n$ et $r$ de 0 à $b$ , $P_{max}(k, r)$ est le profit maximal avec les objets d'indices 0 à $k - 1$ et au plus $r$ unités de ressources. On a $P_{max}(0, r) = 0$ et, pour $0 \le i \le n - 1$ :

P_{max}(i+1, r) = \max\big(P_{max}(i, r),\ P_{max}(i, r - r_i) + p_i\big) \quad \text{si } r_i \le r

et $P_{max}(i+1, r) = P_{max}(i, r)$ si $r_i > r$ . Le sujet imprimait la formule sans ce second cas ; son programme, lui, le traite. On l'a complétée.

def KPprogDynamique(obj, b):
    T = []
    n = len(obj)
    for k in range(n + 1):
        L = []
        for r in range(b + 1):
            L.append(0)
        T.append(L)
    for i in range(n):
        for r in range(b + 1):
            if obj[i][0] <= r:
                T[i + 1][r] = max(T[i][r],
                    T[i][r - obj[i][0]] + obj[i][1])
            else:
                T[i + 1][r] = T[i][r]
    return T[n][b]

Q12. Avec obj = [(2, 3), (1, 4), (4, 4)] et b = 5, donner le tableau T après la création, puis la ligne T[i + 1] à la fin de chacun des trois tours de la boucle sur i. Que renvoie la fonction et à quoi correspond cette valeur ?

Q13. Donner, en la justifiant, la complexité de KPprogDynamique.

On garde la fonction jusqu'à la boucle, et on remplace le return par les lignes suivantes, qui renvoient la solution S = [x0, x1, ...], avec xi égal à 1 si l'objet i est pris, et la valeur T[n][b].

    S = n * [0]
    k = n - 1
    r = b
    while r > 0 and k >= 0 and T[k + 1][r] != 0:
        while k > 0 and T[k + 1][r] == T[k][r]:
            k = k - 1
        S[k] = 1
        r = r - obj[k][0]
        k = k - 1
    return S, T[n][b]

Q14. Donner S, k et r après chaque tour de la boucle while extérieure. La complexité de la fonction change-t-elle ?

Question A. (Question ajoutée.) Un candidat recopie la formule du sujet telle qu'elle était imprimée, sans le test obj[i][0] <= r. Qu'affiche alors le programme pour le même exemple ? Expliquer d'où vient l'écart.

Indications

Q12 : méthode 4. Chaque ligne dépend seulement de la ligne précédente ; remplis-la de gauche à droite.
Q13 : méthode 10. Compte les cases, et le coût d'une case. Le résultat dépend de deux grandeurs.
Q14 : méthode 9. La remontée compare T[k + 1][r] à T[k][r].
Question A : que vaut T[i][-1] en Python ?

Analyse : comment trouver l’idée

Écris la phrase du sous-problème : T[k][r] est le meilleur profit avec les k premiers objets et r unités. La ligne k + 1 se calcule à partir de la ligne k seulement. Pour la remontée, un objet est pris quand la valeur change d'une ligne à la suivante.

Correction détaillée

Q12. Après la création, T contient quatre lignes de six zéros. La ligne T[i + 1] reçoit, pour chaque r, le meilleur des deux choix : laisser l'objet i, ou le prendre s'il tient.

obj = [(2, 3), (1, 4), (4, 4)]
b = 5
print(KPprogDynamique(obj, b))
T = [[0] * (b + 1) for k in range(4)]
for i in range(3):
    for r in range(b + 1):
        T[i + 1][r] = T[i][r]
        if obj[i][0] <= r:
            T[i + 1][r] = max(T[i][r],
                T[i][r - obj[i][0]] + obj[i][1])
    print(T[i + 1])

Le programme affiche :

8
[0, 0, 3, 3, 3, 3]
[0, 4, 4, 7, 7, 7]
[0, 4, 4, 7, 7, 8]

La fonction renvoie T[3][5] = 8, le profit maximal avec les trois objets et 5 unités de ressources : on prend les objets 1 et 2, de ressources $1 + 4 = 5$ et de profit $4 + 4 = 8$ . Le profit 7 de la case T[2][5] est celui des objets 0 et 1 : le troisième objet ne fait gagner qu'une unité de profit, en remplaçant l'objet 0.

Q13. Le tableau a $(n + 1)(b + 1)$ cases ; la création coûte $O(nb)$ , et chaque case de la double boucle se calcule en temps constant : la complexité est en $O(nb)$ . Elle dépend de $n$ et de $b$ : rien ne permet de dire que $b$ est un $O(n)$ .

Q14. Premier tour : k = 2, r = 5. On a T[3][5] = 8 et T[2][5] = 7 : l'objet 2 est pris. Après ce tour, S = [0, 0, 1], k = 1, r = 1. Second tour : T[2][1] = 4 diffère de T[1][1] = 0, l'objet 1 est pris. Après ce tour, S = [0, 1, 1], k = 0, r = 0, et la boucle s'arrête car r est nul.

# renvoie (S, profit maximal) ; S[i] vaut 1 si
# l'objet i est pris
def KPsolution(obj, b):
    n = len(obj)
    T = [[0] * (b + 1) for k in range(n + 1)]
    for i in range(n):
        for r in range(b + 1):
            T[i + 1][r] = T[i][r]
            if obj[i][0] <= r:
                T[i + 1][r] = max(T[i][r],
                    T[i][r - obj[i][0]] + obj[i][1])
    S = n * [0]
    k = n - 1
    r = b
    while r > 0 and k >= 0 and T[k + 1][r] != 0:
        while k > 0 and T[k + 1][r] == T[k][r]:
            k = k - 1
        S[k] = 1
        r = r - obj[k][0]
        k = k - 1
        print(S, k, r)
    return S, T[n][b]

print(KPsolution(obj, b))

Le programme affiche :

[0, 0, 1] 1 1
[0, 1, 1] 0 0
([0, 1, 1], 8)

La remontée fait décroître k à chaque tour des deux boucles, de $n - 1$ à 0 au plus : elle coûte $O(n)$ . La complexité totale reste en $O(nb)$ .

Question A. Sans le test, on calcule T[i][r - obj[i][0]] même quand l'indice est négatif. Python ne signale rien : T[i][-1] est la dernière case de la ligne.

# formule du sujet recopiée sans le cas r_i > r
def KPfaux(obj, b):
    n = len(obj)
    T = [[0] * (b + 1) for k in range(n + 1)]
    for i in range(n):
        for r in range(b + 1):
            T[i + 1][r] = max(T[i][r],
                T[i][r - obj[i][0]] + obj[i][1])
    return T[n][b]

print(KPfaux(obj, b))

Le programme affiche :

Le résultat 11 est impossible : c'est la somme des trois profits, alors que les trois objets demandent 7 unités de ressources pour 5 disponibles. Dès r = 0, la case T[1][0] lit T[0][-2] et compte l'objet 0 pour rien : chaque ligne finit remplie du total des profits déjà vus. Le cas $r_i > r$ n'est pas un détail de rédaction ; il fait partie de la récurrence.

Méthodes à retenir

Une récurrence se donne avec ses cas interdits. En Python, un indice négatif ne lève aucune erreur et fausse le résultat sans bruit. La remontée coûte $O(n)$ et ne change pas le coût total. Voir les méthodes 4, 9, 10 et 13.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 19 méthodes, 21 pièges corrigés, la carte mentale, 36 exercices corrigés, 4 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Voir les offres

Plan du cours

1. Un problème que ni le glouton ni la force brute ne règlent
- 1.1 Charger le camion
- 1.2 Le glouton se trompe
- 1.3 La force brute explose
- 1.4 L'idée de la méthode
2. Découper en sous-problèmes
- 2.1 La phrase qui définit le sous-problème
- 2.2 La récurrence : pris ou laissé
- 2.3 Vérifier à la main
- 2.4 Le Python employé dans ce chapitre
3. Pourquoi la méthode est efficace : deux propriétés
- 3.1 Le chevauchement des sous-problèmes
- 3.2 La sous-structure optimale
- 3.3 Glouton, diviser pour régner, programmation dynamique
4. Version descendante : la mémoïsation
- 4.1 Le principe
- 4.2 Le code
- 4.3 Trace
- 4.4 Avec un tableau rempli d'une valeur impossible
- 4.5 La pile d'appels
- 4.6 Un dictionnaire par appel principal
5. Version ascendante : le tableau
- 5.1 Le principe
- 5.2 L'ordre se lit sur les dépendances
- 5.3 Le code
- 5.4 Le tableau rempli
- 5.5 Les deux versions comparées
6. Reconstruire une solution
- 6.1 La remontée
- 6.2 Égalités et solutions multiples
7. Complexités
- 7.1 Le temps
- 7.2 La mémoire
- 7.3 Une complexité qui dépend de la valeur de la charge
- 7.4 Une mesure
- 7.5 Meilleur et pire cas
8. Un problème à une dimension : rendre la monnaie
- 8.1 Le sous-problème
- 8.2 Le code
- 8.3 Reconstruction
- 8.4 Complexité, et compter au lieu d'optimiser
9. Problèmes à deux dimensions
- 9.1 La partition équilibrée
- 9.2 La plus longue sous-suite commune
- 9.3 La distance d'édition
- 9.4 Un chemin de coût minimal dans une grille
- 9.5 Les tâches pondérées
- 9.6 Des sous-problèmes sur des intervalles
10. Bilan
- 10.1 Les étapes
- 10.2 Tableaux de synthèse
- 10.3 Pour aller plus loin
11. Distances dans un graphe : Floyd-Warshall
- 11.1 Le problème
- 11.2 Le sous-problème
- 11.3 Le code
- 11.4 Trace
- 11.5 Reconstruire un chemin
- 11.6 Poids négatifs

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Reconnaître un problème de programmation dynamique
Définir le sous-problème par une phrase exacte
Établir la récurrence, les cas de base et les cas interdits
Lire une récurrence ou un programme donnés par un sujet
Écrire la version récursive naïve et compter ses appels
Mémoïser avec un dictionnaire
Écrire la version ascendante
Choisir l'ordre de remplissage à partir des dépendances
Reconstruire une solution optimale
Justifier la complexité en temps et en mémoire
Prouver la correction et la terminaison
Comparer glouton et programmation dynamique sur un même problème
Résoudre le sac à dos binaire et la partition équilibrée
Rendre la monnaie et découper une barre
Calculer une plus longue sous-suite commune
Calculer une distance d'édition et une suite d'opérations
Trouver un chemin de coût minimal dans une grille ou une matrice
Résoudre un problème de tâches ou d'intervalles
Calculer toutes les distances d'un graphe par Floyd-Warshall

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (15)

Quatre stratégies à reconnaître
Le sac du fret
Rendre 6 avec 1, 3 et 4
L'arbre des appels d'un rendu naïf
Mémoïser une recherche exhaustive
Sous-suite ou facteur
La matrice de Levenshtein à la main
Les chemins d'une grille
Le triangle de Pascal en tableau
Ce que calcule la version descendante
Quatre tableaux mal créés
Les étapes du camion
Trois complexités à justifier
Compter ou optimiser
Floyd-Warshall à la main

Entraînement (16)

Découper une barre, exactement
La découpe d'un ruban
Le loueur de skis
La plus longue sous-suite croissante
Le plus grand carré de cases libres
Répartir des caisses en deux lots
Les créneaux pondérés de la balance
Distance de Levenshtein et suite d'opérations
Une distance sans substitution
Les poteaux
Mémoïser sur un graphe de dépendances
Le dictionnaire qui se souvient trop
Mesurer les trois versions
Reconstruire avec un tableau des choix
Prouver une récurrence
Distances, chemins et cycle de poids négatif

Approfondissement (5)

Le décodage le plus probable
Placer les blocs d'une ligne
Une seule ligne de mémoire
Toutes les solutions optimales
Le jeu de Röckse par programmation dynamique

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Réduire une image : le chemin vertical de coût minimal
CNC 2025, filières MP et PSI, épreuve d'informatique, partie II « Réduction d'image, algorithme Seam Carving », section A « Chemin vertical dans une matrice », questions 25 à 28, complétée
Le produit d'une chaîne de matrices
CNC 2024, filières MP et PSI, épreuve d'informatique, partie I « Programmation et calcul scientifique », « Produit d'une chaîne matricielle », sections A « Calcul du nombre minimum de multiplications dans le produit d'une chaîne matricielle » et B « Recherche du parenthésage optimal », questions 7 à 10, complétée
La plus longue sous-séquence commune
CNC 2022, filière MP, épreuve d'informatique, partie III « Plus Longue Sous Séquence Commune », questions 2 à 6, complétée
Justifier un paragraphe
Mines-Ponts 2023, filières MP, PC et PSI, épreuve d'informatique commune, partie VI « Justification d'un paragraphe », questions 22 à 26, complétée

Questions fréquentes

Quelle est la différence entre un algorithme glouton et la programmation dynamique ?

Le glouton fait un seul choix à chaque étape, fixé par un critère, sans jamais le remettre en cause : il n'est exact que si son choix figure toujours dans une solution optimale. La programmation dynamique compare tous les choix et garde le meilleur : elle est exacte dès que la sous-structure optimale est vraie. Pour charger un camion de 15 quintaux, le glouton par rapport valeur sur poids donne 117 alors que l'optimum vaut 132 ; pour rendre 6 avec les pièces 1, 3 et 4, le glouton rend $4 + 1 + 1$ , trois pièces, alors que $3 + 3$ en fait deux. Les deux méthodes reposent sur la sous-structure optimale ; le glouton exige en plus que son choix soit toujours le bon.

Mémoïsation ou version ascendante : laquelle choisir ?

Les deux donnent le même résultat et ont la même complexité dans le pire cas. La version descendante garde la fonction récursive : elle range chaque réponse dans un dictionnaire, passé en argument et créé vide à chaque appel principal, et le consulte avant de calculer ; elle ne calcule que les sous-problèmes rencontrés, mais Python limite la profondeur des appels à 1000 par défaut. La version ascendante remplit un tableau des plus petits sous-problèmes aux plus grands, dans un ordre qui respecte les dépendances : elle calcule toutes les cases, sans récursion ni limite de pile, et la reconstruction s'y lit directement.

Quelle est la complexité du sac à dos en programmation dynamique ?

Avec $n$ objets et une charge $c$ , il y a $(n + 1)(c + 1)$ sous-problèmes, chacun calculé en temps constant à partir de deux cases : $O(nc)$ en temps et en mémoire, pour les deux versions. Comme une ligne ne dépend que de la précédente, deux lignes suffisent pour la valeur optimale, en $O(c)$ de mémoire, mais la reconstruction est perdue. Ce coût dépend de la valeur de $c$ , pas de sa longueur d'écriture : la même charge comptée en kilogrammes au lieu de quintaux passe de 15 à 1500 colonnes. Au programme marocain, le meilleur cas de la version mémoïsée, tous les objets trop lourds, fait $n + 1$ appels, en $\Theta(n)$ .

Comment reconstruire une solution optimale à partir du tableau ?

Le tableau donne la valeur optimale, pas les objets. On remonte depuis la case T[n][c] : si T[i][r] diffère de T[i - 1][r], l'objet $i - 1$ a été pris, on le marque et l'on continue avec la charge $r - p$ ; sinon, on continue avec la même charge. La remontée coûte $O(n)$ et ne change pas le coût total. En cas d'égalité entre les deux choix, la règle de remontée détermine la solution trouvée : un sujet qui donne un exemple impose souvent la sienne. On peut aussi ranger le choix fait pour chaque case dans un second tableau.

Comment calculer une plus longue sous-suite commune ou une distance d'édition ?

Les deux portent sur les préfixes et regardent les derniers éléments. Pour la plus longue sous-suite commune, T[i][j] vaut T[i - 1][j - 1] + 1 si les derniers éléments sont égaux, sinon le plus grand de T[i - 1][j] et T[i][j - 1], avec des zéros sur les bords. Pour la distance d'édition, $D[i][j]$ est le minimum de $D[i - 1][j - 1] + \delta$ , $D[i - 1][j] + 1$ et $D[i][j - 1] + 1$ , où $\delta$ vaut 0 si les deux dernières lettres sont égales et 1 sinon, avec $D[i][0] = i$ et $D[0][j] = j$ . Les deux tableaux coûtent $O(nm)$ en temps et en mémoire, la remontée $O(n + m)$ . De MAJHOUL à MEDJOUL, la distance vaut 3.

Floyd-Warshall est-il au programme de MP et PSI ?

Dans ce chapitre, il est traité pour les classes françaises : MP, PSI, PC et PT. Au Maroc, il vient avec les graphes. L'algorithme donne les distances entre toutes les paires de sommets : $d_k(i, j)$ est la longueur d'un plus court chemin de $i$ à $j$ dont les sommets intermédiaires sont parmi $0, \ldots, k - 1$ , et $d_{k+1}(i, j) = \min(d_k(i, j), d_k(i, k) + d_k(k, j))$ , avec $d_0$ égale à la matrice des poids. Une seule matrice suffit ; le coût est $O(n^3)$ en temps et $O(n^2)$ en mémoire. Il reste juste avec des poids négatifs, sans cycle de poids négatif ; un tel cycle rend négative une case de la diagonale.

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit pour les filières dont il est l'un des premiers chapitres. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.

Programmation dynamique : cours, mémoïsation, sac à dos et exercices corrigés de prépa

Ce que tu sauras faire

L'essentiel : Le sac à dos binaire, modèle de tout le chapitre Extrait gratuit

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Plan du cours

Les méthodes du chapitre

Les exercices corrigés

Application directe (15)

Entraînement (16)

Approfondissement (5)

Les problèmes de concours

Questions fréquentes

Comment y accéder

Toute ta prépa au même endroit