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 un
nescalier 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 (la
nn-ième marche), cela peut sembler compliqué.Mais si nous changeons de perspective :Pour atteindre le
nn. 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 :
- 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.
- 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
"""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
"""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
"""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
"""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éfinissons
dp[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 de
i=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
"""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
- Définir l'état:
dp[i]représente la constitution du montant totalile nombre minimum de pièces nécessaires. - équation de transition d'état: Pour le montant
i, 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。 - 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. - Ordre de calcul: de bas en haut, à partir de
i=1Calculer jusqu'ài=amount。
Implémentation du code
Exemple
"""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éfinition
dp[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 tous
dp[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éfinition
dp[i]comme "avec leila longueur de la plus longue sous-séquence croissante se terminant par le nombre". - Pour chaque
i, il faut parcourirjfrom0ài-1, sinums[i] > nums[j], puisdp[i] = max(dp[i], dp[j] + 1)。 - Initialement, chaque
dp[i]au moins 1 (ne contenant que lui-même).
