Aller au contenu principal

Programmation dynamique

#Programmation dynamique

La programmation dynamique est une technique algorithmique utilisée pour résoudre des problèmes d'optimisation en décomposant le problème en sous-problèmes plus simples, et en stockant les résultats de ces sous-problèmes pour éviter de les recalculer.

#Concepts clés

  • Sous-structures optimales : La solution optimale d'un problème contient les solutions optimales de ses sous-problèmes.
  • Chevauchement de sous-problèmes : Le même sous-problème est résolu plusieurs fois. La programmation dynamique stocke les résultats pour éviter les recalculs.

#Mémoïsation vs Tabulation

  • Mémoïsation : Top-down. On utilise la récursion et on stocke les résultats dans une table.
  • Tabulation : Bottom-up. On remplit un tableau de manière itérative.

#Fibonacci (mémoïsation)



#Fibonacci (tabulation)


pythonpython
1def fib_tabulation(n):2    if n < 2:3        return n4    dp = [0] * (n + 1)5    dp[1] = 16    for i in range(2, n + 1):7        dp[i] = dp[i - 1] + dp[i - 2]8    return dp[n]9 10print([fib_tabulation(i) for i in range(12)])




#Rendu de monnaie


Problème : Trouver le nombre minimal de pièces pour rendre une certaine somme.


pythonpython
1def coin_change(coins, amount):2    dp = [float('inf')] * (amount + 1)3    dp[0] = 04    for coin in coins:5        for x in range(coin, amount + 1):6            dp[x] = min(dp[x], dp[x - coin] + 1)7    return dp[amount] if dp[amount] != float('inf') else -18 9coins = [1, 3, 4]10amount = 611print(coin_change(coins, amount))  # 2 (3 + 3)




#Sac à dos 0/1 (tabulation)


pythonpython
1def knap(values, weights, W):2    n = len(values)3    dp = [[0]*(W+1) for _ in range(n+1)]4    for i in range(1, n+1):5        for w in range(W+1):6            dp[i][w] = dp[i-1][w]7            if weights[i-1] <= w:8                dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])9    return dp[n][W]10 11values = [60, 100, 120]12weights = [10, 20, 30]13W = 5014print(knap(values, weights, W))  # 220




#Exercices


    

  1. Chaîne de multiplication de matrices : Trouver le nombre minimal de multiplications scalaires nécessaires pour multiplier une chaîne de matrices.
    2. 

  2. Plus longue sous-séquence commune (LCS) : Trouver la plus longue sous-séquence commune à deux chaînes.
    3. 

  3. Nombre de chemins dans une grille : Trouver le nombre de chemins possibles dans une grille pour aller du coin supérieur gauche au coin inférieur droit.
    4. 



#Exercice : Plus longue sous-séquence commune (LCS)


Implémentez l'algorithme de la plus longue sous-séquence commune (LCS) en utilisant la programmation dynamique.


Instructions


    

  1. Créez une matrice dp de taille (m+1) x (n+1) où m et n sont les longueurs des deux chaînes.
    2. 

  2. Initialisez la première ligne et la première colonne à 0.
    3. 

  3. Pour chaque cellule dp[i][j], si les caractères des deux chaînes sont égaux, dp[i][j] = dp[i-1][j-1] + 1. Sinon, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
    4. 

  4. La valeur dp[m][n] contiendra la longueur de la LCS.
    5. 



Exemple de code


pythonpython
1def lcs(X, Y):2    m = len(X)3    n = len(Y)4    # Création de la matrice DP5    dp = [[0] * (n + 1) for _ in range(m + 1)]6    7    # Remplissage de la matrice8    for i in range(1, m + 1):9        for j in range(1, n + 1):10            if X[i - 1] == Y[j - 1]:11                dp[i][j] = dp[i - 1][j - 1] + 112            else:13                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])14    




Complexité
    

  • Fibonacci (mémoïsation/tabulation): O(n).
    • 

  • Rendu de monnaie: O(amount * nombre de pièces).
    • 

  • Sac à dos 0/1: O(n * W).
    • 

  • LCS: O(m * n).
    •