Programmation dynamique

La programmation dynamique (en anglais : Dynamic programming, abrégée en DP) est une méthode utilisée en mathématiques, en sciences de la gestion, en informatique, en économie et en bio-informatique qui résout des problèmes complexes en décomposant le problème d'origine en sous-problèmes relativement simples.

Imaginez que vous montez unnescalier de n marches. Chaque fois, vous pouvez monter1marche ou2marches.

Alors, combien de façons différentes y a-t-il de monter jusqu'au sommet du bâtiment ?

Si vous partez de l'objectif le plus haut (lann-ième marche), cela peut sembler compliqué.

Mais si nous changeons de perspective :Pour atteindre lenn. Pour atteindre la marche n, vous ne pouvez quen-1monter d'une marche depuis la marche n-1, ou depuis lan-2niveau en montant deux marches.. Donc, pour atteindre lenLe nombre de façons d'atteindre la marche n est égal au nombre de façons d'atteindre la marchen-1n-1 plus le nombre de façons d'atteindre la marchen-2niveau, le nombre de façons.

Ce type deDécomposer un grand problème en plusieurs sous-problèmes qui se chevauchent, et éviter les calculs répétés en stockant les solutions des sous-problèmes, ce qui permet de résoudre efficacement le problème d'origine.La méthode est la programmation dynamique (DP en abrégé).

Idée centrale

Le cœur de la programmation dynamique est demémoriser les solutions déjà calculées. 。

La programmation dynamique est généralement utilisée pour résoudre des problèmes ayant les propriétés suivantes :

  1. sous-problèmes qui se chevauchent: Pendant le processus de résolution récursive, le même sous-problème peut être calculé plusieurs fois.
  2. Sous-structure optimale: La solution optimale d'un problème contient les solutions optimales de ses sous-problèmes.

Nous pouvons utiliser un organigramme simple pour comprendre l'approche de résolution de problèmes de la programmation dynamique :

La figure ci-dessus montre les étapes typiques de résolution d'un problème de programmation dynamique : commencez par définir le problème, trouvez la structure des sous-problèmes par analyse, puis formalisez-la avec des états et des équations de transition d'état, et enfin obtenez la réponse grâce à des conditions initiales claires et à un ordre de calcul clair.


De la récursion à la programmation dynamique : le problème de la montée des escaliers

utilisons le classique"Climbing Stairs"problème pour expérimenter le processus d'optimisation de la récursion à la programmation dynamique.

Description du problème

Supposons que vous montez des escaliers. Vous deveznmarches avant de pouvoir atteindre le sommet. Chaque fois, vous pouvez monter1ou2marches. De combien de façons différentes pouvez-vous monter jusqu'au sommet ?

Méthode 1 : récursion par force brute (inefficace)

D'après l'analyse du début, nous pouvons directement écrire la formule récursive :f(n) = f(n-1) + f(n-2)où,f(1) = 1, f(2) = 2。

Exemple

def climb_stairs_recursive(n: int) -> int:
    """Solution récursive"""
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# Test
print(f"Nombre de façons de monter jusqu'à la 5e marche (récursion) : {climb_stairs_recursive(5)}")  # Sortie : 8

Analyse des inconvénients: Cette récursion implique une grande quantité de calculs répétés. Par exemple, le calculf(5)nécessitef(4)etf(3), le calcul def(4)nécessite à son tourf(3)etf(2), icif(3)Il est calculé deux fois. Lorsquenn est grand, la complexité temporelle est exponentielle.O(2^n), ce qui est extrêmement inefficace.

Méthode 2 : Récursion avec mémoïsation (descendante)

Nous pouvons utiliser un tableau (un « memo ») pour stocker les résultats déjà calculés et éviter les calculs répétés.

Exemple

def climb_stairs_memo(n: int) -> int:
    """Récursion avec mémoïsation (descendante)"""
    # Initialiser la table de mémoïsation ; -1 signifie non calculé
    memo = [-1] * (n + 1)
   
    def helper(x: int) -> int:
        # Cas de base
        if x == 1:
            return 1
        if x == 2:
            return 2
        # Si déjà calculé, renvoyer directement le résultat
        if memo[x] != -1:
            return memo[x]
        # Sinon, le calculer et le stocker dans la table de mémoïsation
        memo[x] = helper(x - 1) + helper(x - 2)
        return memo[x]
   
    return helper(n)

print(f"Nombre de façons de monter jusqu'à la 5e marche (mémoïsation) : {climb_stairs_memo(5)}")  # Sortie : 8

La complexité temporelle de cette méthode est réduite àO(n), car chaque sous-problème n'est calculé qu'une seule fois. La complexité spatiale estO(n). Il s'agit déjà d'une approche de programmation dynamique, appelée"top-down"ou"recherche mémoïsée"。

Méthode 3 : tableau itératif (de bas en haut, DP standard)

Nous partons directement du plus petit sous-problème et itérons étape par étape jusqu'au problème d'origine. Généralement, un tableau est utilisédppour stocker les états.

Exemple

def climb_stairs_dp(n: int) -> int:
    """Programmation dynamique (de bas en haut)"""
    if n <= 2:
        return n
    # 1. Définir le tableau d'états : dp[i] représente le nombre de façons de monter jusqu'à la i-ème marche
    dp = [0] * (n + 1)
    # 2. Déterminer les conditions initiales
    dp[1] = 1
    dp[2] = 2
    # 3. Transition d'état : déduire récursivement selon l'équation de transition d'état
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    # 4. Retourner le résultat final
    return dp[n]

print(f"Nombre de façons de monter jusqu'à la 5e marche (DP) : {climb_stairs_dp(5)}")  # Sortie : 8

Méthode 4 : optimisation de l'espace (tableau roulant)

Observer l'équation de transition d'étatdp[i] = dp[i-1] + dp[i-2], nous constatons que l'état actuel ne dépend que des deux états précédents. Par conséquent, nous n'avons pas besoin de stocker l'intégralité dudptableau ; utilisez simplement deux variables pour effectuer une mise à jour glissante.

Exemple

def climb_stairs_optimized(n: int) -> int:
    """Programmation dynamique (version optimisée en espace)"""
    if n <= 2:
        return n
    # Utiliser seulement deux variables pour représenter dp[i-1] et dp[i-2]
    prev, curr = 1, 2  # Correspondent à dp[1], dp[2]
    for i in range(3, n + 1):
        # Calculer la nouvelle valeur courante
        new_curr = prev + curr
        # Mise à jour glissante des variables, en préparation de la prochaine itération de la boucle
        prev, curr = curr, new_curr
    return curr

print(f"Nombre de façons de monter à la 5e marche (programmation dynamique optimisée) : {climb_stairs_optimized(5)}")  # Sortie : 8

Après optimisation, la complexité spatiale passe deO(n)réduite àO(1)。


Cadre de résolution de problèmes de programmation dynamique

À travers le problème de montée d'escaliers, nous pouvons résumer un processus universel en quatre étapes pour résoudre des problèmes de programmation dynamique :

Étape 1 : Définir l'état

Utiliser un ou plusieurs tableaux (généralement appelésdp) pour représenter les solutions des sous-problèmes. La clé est de bien déterminerdp[i]oudp[i][j]Que représente-t-il ?

Dans le problème de montée d'escaliers, nous définissonsdp[i]comme "monter à laile nombre total de façons d'atteindre la marche n.

Étape 2 : Déterminer l'équation de transition d'état

trouverdp[i]avec l'état précédent (tel quedp[i-1], dp[i-2]la relation entre eux. C'est le cœur et la difficulté de la programmation dynamique.

Dans le problème de l'escalier, l'équation de transition d'état est :dp[i] = dp[i-1] + dp[i-2]。

Étape 3 : Déterminer les conditions initiales (cas de base).

Les solutions des plus petits sous-problèmes indivisibles. C'est le point de départ de la récurrence et il doit être défini manuellement.

Dans le problème de l'escalier, les conditions initiales sont :dp[1] = 1, dp[2] = 2。

Étape 4 : Déterminer l'ordre de calcul et calculer

Déterminez s'il s'agit d'une approche "descendante" (récursion avec mémoïsation) ou "ascendante" (récurrence itérative), et assurez-vous que lors du calcul dedp[i], tous les sous-problèmes dont il dépend ont déjà été calculés.

Dans le problème de l'escalier, nous adoptons une approche ascendante, en partant dei=3boucler jusqu'ài=n。


Exemple classique : suite de Fibonacci

La suite de Fibonacci est l'exemple le plus direct de programmation dynamique ; sa définition est elle-même l'équation de transition d'état.

Problème: trouver le n-ième nombre de Fibonaccinterme.F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)

Exemple

def fibonacci(n: int) -> int:
    """Calcule les nombres de Fibonacci en utilisant la programmation dynamique"""
    if n < 2:
        return n
    # Implémentation optimisée en espace
    prev, curr = 0, 1  # F(0), F(1)
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Données de test
test_n = 10
print(f"Le terme n° {test_n} de la suite de Fibonacci est : {fibonacci(test_n)}")  # Sortie : 55

Exemple avancé : rendu de monnaie

Il s'agit d'un problème plus typique qui démontre une sous-structure optimale.

Description du problème: étant donné un tableau d'entierscoins, représentant des pièces de différentes dénominations, et un entieramount, représentant le montant total. Calculez et renvoyez le nombre minimum de pièces nécessaires pour constituer le montant total. Si aucune combinaison de pièces ne peut constituer le montant total, renvoyez-1. Vous pouvez supposer que la quantité de chaque pièce est illimitée.

Analyse du problème et conception de la programmation dynamique

  1. Définir l'état:dp[i]représente la constitution du montant totalile nombre minimum de pièces nécessaires.
  2. équation de transition d'état: Pour le montanti, nous pouvons parcourir chaque dénomination de piècecoin. Sicoin <= i, puis en constituant le montantiUne façon possible est : d'abord constituer le montanti - coin, puis ajouter une piècecoindénomination de la pièce. Ce que nous devons trouver, c'est le minimum parmi toutes les possibilités. Par conséquent, l'équation peut s'écrire :dp[i] = min(dp[i], dp[i - coin] + 1), pour toutes celles qui satisfontcoin <= idecoin。
  3. Conditions initiales:dp[0] = 0, constituer le montant 0 nécessite 0 pièce. Les autresdp[i]initialisé à un très grand nombre (par ex.amount + 1oufloat('inf')), ce qui signifie qu'il ne peut pas être constitué pour le moment.
  4. Ordre de calcul: de bas en haut, à partir dei=1Calculer jusqu'ài=amount。

Implémentation du code

Exemple

def coin_change(coins: list, amount: int) -> int:
    """Rendu de monnaie - Programmation dynamique"""
    # Initialiser le tableau dp, où dp[i] représente le nombre minimum de pièces pour le montant i
    # Définir une valeur initiale inatteignable amount + 1
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # Lorsque le montant est 0, 0 pièce est nécessaire
   
    # Boucle externe : parcourir tous les états de montant
    for i in range(1, amount + 1):
        # Boucle interne : parcourir tous les choix de pièces
        for coin in coins:
            # Si la valeur de la pièce actuelle est inférieure ou égale au montant actuel, envisager d'utiliser cette pièce
            if coin <= i:
                # Transition d'état : dp[i] est la solution sans utiliser la pièce actuelle et
                # la plus petite valeur parmi les solutions utilisant la pièce actuelle (c'est-à-dire dp[i-coin] + 1)
                dp[i] = min(dp[i], dp[i - coin] + 1)
   
    # Si dp[amount] n'a pas été mis à jour (toujours la valeur initiale), cela signifie que le montant ne peut pas être constitué
    return dp[amount] if dp[amount] <= amount else -1

# Données de test
coins = [1, 2, 5]
amount = 11
print(f"Le nombre minimum de pièces nécessaires pour constituer le montant total {amount} est : {coin_change(coins, amount)}")  # Sortie : 3 (5+5+1)

Exercices pratiques

Veuillez essayer de résoudre les problèmes suivants de manière indépendante pour consolider votre compréhension de la programmation dynamique :

Exercice 1 : Somme maximale d'un sous-tableau

Étant donné un tableau d'entiersnums, veuillez trouver un sous-tableau contigu ayant la somme maximale, et renvoyer sa somme maximale.

Exemple:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6。

Indice:

  • définitiondp[i]comme "avec leila somme maximale d'un sous-tableau contigu se terminant par l'élément".
  • équation de transition d'état :dp[i] = max(nums[i], dp[i-1] + nums[i])。
  • La réponse finale est le maximum de tousdp[i]le maximum parmi eux.

Exercice 2 : Plus longue sous-séquence croissante

Étant donné un tableau d'entiersnums, trouvez la longueur de la plus longue sous-séquence strictement croissante.

Exemple:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4。

Indice:

  • définitiondp[i]comme "avec leila longueur de la plus longue sous-séquence croissante se terminant par le nombre".
  • Pour chaquei, il faut parcourirjfrom0ài-1, sinums[i] > nums[j], puisdp[i] = max(dp[i], dp[j] + 1)。
  • Initialement, chaquedp[i]au moins 1 (ne contenant que lui-même).
autres extensions