La programmation dynamique est une technique algorithmique utilisée pour résoudre des problèmes d'optimisation en les divisant en sous-problèmes plus petits et en stockant les résultats de ces sous-problèmes pour éviter de les recalculer plusieurs fois.

Étapes de base pour résoudre un problème avec la programmation dynamique :

1. Définir le problème : Il est important de bien comprendre le problème et de définir clairement l'objectif à atteindre.
2. Identifier la structure récursive : La plupart des problèmes résolus avec la programmation dynamique ont une structure récursive, ce qui signifie que la solution d'un problème peut être exprimée en termes de solutions de sous-problèmes plus petits. Identifiez cette structure récursive pour pouvoir l'exploiter.
3. Définir la fonction de récurrence : La fonction de récurrence définit la relation entre le problème initial et ses sous-problèmes. Elle permet de décomposer le problème en sous-problèmes plus petits et de déterminer comment combiner les solutions de ces sous-problèmes pour obtenir la solution globale.
4. Mémoriser les résultats intermédiaires : Pour éviter de recalculer les mêmes sous-problèmes plusieurs fois, utilisez une structure de données pour stocker les résultats intermédiaires. Cela permet de réduire considérablement le temps d'exécution de l'algorithme.
5. Déterminer l'ordre de calcul : La programmation dynamique peut être réalisée de manière ascendante (bottom-up) ou descendante (top-down). Dans l'approche ascendante, les sous-problèmes sont résolus de manière séquentielle, en commençant par les plus petits. Dans l'approche descendante, on commence par le problème initial et on résout les sous-problèmes au fur et à mesure qu'ils se présentent.
6. Implémenter la solution : Utilisez le langage de programmation Python pour mettre en œuvre l'algorithme de programmation dynamique. Assurez-vous de bien gérer la mémorisation des résultats intermédiaires et de suivre l'ordre de calcul défini précédemment.

Exemple de problème résolu avec la programmation dynamique :

1️⃣. Calcul du n-ième nombre de Fibonacci

La suite de Fibonacci est définie comme suit :

Voici une implémentation de la solution en utilisant la programmation dynamique :

def fibonacci(n):
    fib = [0, 1]  # Tableau pour stocker les résultats intermédiaires

    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])  # Calcul du nombre de Fibonacci
    return fib[n]

# Exemple d'utilisation
n = 10
result = fibonacci(n)
print(f"Le {n}-ième nombre de Fibonacci est : {result}")

2️⃣. Calcul du plus long sous-séquence commune (LCS)

Le problème consiste à trouver la plus longue sous-séquence commune entre deux chaînes de caractères.

Voici une implémentation de la solution en utilisant la programmation dynamique :

def longest_common_subsequence(str1, str2):
    m = len(str1)
    n = len(str2)

    # Création d'un tableau pour stocker les résultats intermédiaires
    lcs = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                lcs[i][j] = lcs[i - 1][j - 1] + 1
            else:
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])

    return lcs[m][n]

Exemple de problème résolu avec la programmation dynamique :

3️⃣. Calcul du sac à dos (Knapsack)

Le problème du sac à dos consiste à déterminer la meilleure combinaison d'objets à mettre dans un sac à dos, en maximisant la valeur totale des objets tout en respectant la capacité du sac.

Voici une implémentation de la solution en utilisant la programmation dynamique :

def knapsack(capacity, weights, values):
    n = len(weights)
    # Création d'un tableau pour stocker les résultats intermédiaires
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][capacity]

# Exemple d'utilisation
capacity = 10
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
result = knapsack(capacity, weights, values)
print(f"La valeur maximale du sac à dos est : {result}")

4️⃣. Calcul du sac à dos (Knapsack)

Le problème consiste à trouver la plus longue sous-chaîne commune entre deux chaînes de caractères.

Voici une implémentation de la solution en utilisant la programmation dynamique :

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)

    # Création d'un tableau pour stocker les résultats intermédiaires
    lcs = [[0] * (n + 1) for _ in range(m + 1)]

    max_length = 0
    end_index = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                lcs[i][j] = lcs[i - 1][j - 1] + 1

                if lcs[i][j] > max_length:
                    max_length = lcs[i][j]
                    end_index = i

    longest_substring = str1[end_index - max_length: end_index]
    return longest_substring

# Exemple d'utilisation
str1 = "abcdxyz"
str2 = "xyzabcd"
result = longest_common_substring(str1, str2)
print(f"La plus longue sous-chaîne commune est : {result}")

Remarque

Ces exemples illustrent différentes applications de la programmation dynamique en utilisant Python. Assurez-vous de bien comprendre la logique derrière chaque algorithme et de vous familiariser avec les concepts clés tels que la mémorisation des résultats intermédiaires et la décomposition du problème en sous-problèmes plus petits.

Exercices - corrigés: Programmation dynamique avec Python

Exercice 1: ★ ★ ★ ☆ ☆

Considérons une grille de taille m x n. On se déplace de la case supérieure gauche à la case inférieure droite en ne se déplaçant que vers la droite ou vers le bas. Écrivez une fonction grid_paths(m, n) qui prend en argument les dimensions de la grille m et n, et renvoie le nombre de chemins possibles pour se déplacer de la case supérieure gauche à la case inférieure droite.

def grid_paths(m, n):
    # Création d'un tableau pour stocker les résultats intermédiaires
    paths = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == 1 or j == 1:
                paths[i][j] = 1
            else:
                paths[i][j] = paths[i - 1][j] + paths[i][j - 1]
    return paths[m][n]

# Test de la fonction
print(grid_paths(3, 3))  # Résultat attendu : 6
print(grid_paths(2, 3))  # Résultat attendu : 3

Exercice 2: ★ ★ ★ ☆ ☆

Supposons que vous ayez un sac à dos de capacité maximale C et une liste d'objets avec leur poids weights et leur valeur values. Écrivez une fonction knapsack(C, weights, values) qui utilise la programmation dynamique pour déterminer la valeur maximale que vous pouvez emporter dans le sac.

def knapsack(C, weights, values):
    n = len(weights)

    # Création d'un tableau pour stocker les résultats intermédiaires
    dp = [[0] * (C + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, C + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][C]

# Test de la fonction
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
C = 7
print(knapsack(C, weights, values))  # Résultat attendu : 10

Exercice 3: ★ ★ ☆ ☆ ☆

Étant donné deux chaînes de caractères str1 et str2, trouvez la longueur du plus long sous-mot commun. Un sous-mot est une séquence de caractères qui apparaît dans le même ordre relatif, mais pas nécessairement consécutif.

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)

    # Création d'un tableau pour stocker les résultats intermédiaires
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    max_length = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_length = max(max_length, dp[i][j])

    return max_length

# Test de la fonction
str1 = "abcdxyz"
str2 = "xyzabcd"
print(longest_common_substring(str1, str2))  # Résultat attendu : 4

Exercice 4: ★ ★ ★ ☆ ☆

Un dérangement est une permutation des éléments d'un ensemble où aucun élément n'est à sa position d'origine. Par exemple, pour un ensemble de 3 éléments {1, 2, 3}, les dérangements possibles sont {2, 3, 1} et {3, 1, 2}. Écrivez une fonction \(countderangements(n)\);qui renvoie le nombre de dérangements possibles pour un ensemble de n éléments.

def count_derangements(n):
    # Création d'un tableau pour stocker les résultats intermédiaires
    dp = [0] * (n + 1)

    dp[2] = 1

    for i in range(3, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])

    return dp[n]

# Test de la fonction
print(count_derangements(3))  # Résultat attendu : 2
print(count_derangements(4))  # Résultat attendu : 9

Exercice 5: ★ ★ ★ ☆ ☆

Supposons que vous ayez un ensemble de pièces de monnaie de différentes valeurs, par exemple [1, 2, 5]. Écrivez une fonction coin_change(coins, amount) qui utilise la programmation dynamique pour déterminer le nombre de façons différentes de former une somme amount en utilisant les pièces disponibles.

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

# Test de la fonction
coins = [1, 2, 5]
amount = 10
print(coin_change(coins, amount))  # Résultat attendu : 10

Exercice 6: ★ ☆ ☆ ☆ ☆

Supposons que vous ayez une grille de taille m x n et que vous souhaitiez vous déplacer de la case supérieure gauche à la case inférieure droite. Vous ne pouvez vous déplacer que vers la droite ou vers le bas. Écrivez une fonction unique_paths(m, n) qui utilise la programmation dynamique pour déterminer le nombre de chemins uniques pour atteindre la case inférieure droite depuis la case supérieure gauche.

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        dp[i][0] = 1

    for j in range(n):
        dp[0][j] = 1

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

# Test de la fonction
m = 3
n = 3
print(unique_paths(m, n))  # Résultat attendu : 6

Exercice 7: ★ ★ ★ ☆ ☆

Étant donné une liste d'entiers, trouvez la longueur de la plus longue sous-séquence croissante. Une sous-séquence est une séquence qui peut être dérivée de la liste initiale en supprimant certains éléments sans changer l'ordre des éléments restants.

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# Test de la fonction
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(nums))  # Résultat attendu : 4