La programmation dynamique ( DP ) est une technique qui résout certains types particuliers de problèmes en temps polynomial. Les solutions de programmation dynamique sont plus rapides que la méthode brute exponentielle et peuvent être facilement prouvées pour leur exactitude. Avant d'étudier comment penser dynamiquement pour un problème, nous devons apprendre :
- chevauchement des sous problémes
- optimalité des sous problémes
Étapes pour résoudre un DP 1) Identifier s'il s'agit d'un problème de DP 2) Choisissez une expression d'état avec moins de paramètres 3) Formuler la relation d'état 4) Faites une tabulation (ou ajoutez une mémorisation)
Étape 1 : Comment classer un problème comme un problème de programmation dynamique ?
- En règle générale, tous les problèmes qui nécessitent de maximiser ou de minimiser certaines quantités ou les problèmes de comptage qui disent de compter les arrangements dans certaines conditions ou certains problèmes de probabilité peuvent être résolus en utilisant la programmation dynamique.
- Tous les problèmes de programmation dynamique satisfont la propriété de sous-problèmes qui se chevauchent et la plupart des problèmes dynamiques classiques satisfont également la propriété de sous-structure optimale. Une fois que nous observons ces propriétés dans un problème donné, assurez-vous qu'il peut être résolu en utilisant DP.
Étape 2 : Décider de l'état
Les problèmes de DP concernent tous l'état et sa transition. C'est l'étape la plus élémentaire qui doit être effectuée avec beaucoup de soin car la transition d'état dépend du choix de la définition d'état que vous faites. Voyons donc ce que nous entendons par le terme « État ».
État Un état peut être défini comme l'ensemble de paramètres qui peuvent identifier de manière unique une certaine position ou position dans le problème donné. Cet ensemble de paramètres doit être aussi petit que possible pour réduire l'espace d'état.
Par exemple : Dans notre fameux probléme du sac à dos , nous définissons notre état par deux paramètres index et poids c'est-à-dire DP[index][poids]. Ici, DP[index][weight] nous indique le profit maximal qu'il peut réaliser en prenant des articles de la plage 0 à l'indice ayant la capacité d'un sac à peser. Par conséquent, ici, les paramètres index et poids peuvent identifier de manière unique un sous-problème pour le problème du sac à dos.
Ainsi, notre première étape consistera à décider d'un état pour le problème après avoir identifié que le problème est un problème DP.
Comme nous le savons, DP consiste à utiliser des résultats calculés pour formuler le résultat final.
Ainsi, notre prochaine étape sera de trouver une relation entre les états précédents pour atteindre l'état actuel.
Étape 3 : Formulation d'une relation entre les états
Cette partie est la partie la plus difficile de la résolution d'un problème DP et nécessite beaucoup d'intuition, d'observation et de pratique. Comprenons-le en considérant un exemple de problème
Étant donné 3 nombres {1, 3, 5}, nous devons indiquer
le nombre total de façons dont nous pouvons former un nombre 'N'
en utilisant la somme des trois nombres donnés.
(permettant des répétitions et des arrangements différents).
Le nombre total de façons de former 6 est : 8
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
Réfléchissons dynamiquement à ce problème. Donc, tout d'abord, nous décidons d'un état pour le problème donné. Nous prendrons un paramètre n pour décider de l'état car il peut identifier de manière unique tout sous-problème. Ainsi, notre état dp ressemblera à state. Ici, state
signifie le nombre total d'arrangements pour former n en utilisant {1, 3, 5} comme éléments.
Maintenant, nous devons calculer state.
Comment faire?
C'est donc ici que l'intuition entre en action. Comme nous ne pouvons utiliser que 1, 3 ou 5 pour former un nombre donné. Supposons que l'on connaisse le résultat pour n = 1,2,3,4,5,6 ; étant termilogistique disons que nous connaissons le résultat pour l'
état (n = 1), l'état (n = 2), l'état (n = 3) ……… l'état (n = 6)
Maintenant, nous souhaitons connaître le résultat de la état (n = 7). Vous voyez, nous ne pouvons additionner que 1, 3 et 5. Nous pouvons maintenant obtenir une somme totale de 7 par les 3 façons suivantes :
1) Ajouter 1 à toutes les combinaisons possibles d'état (n = 6)
Ex : [ (1+1+1+1+1+1) + 1]
[ (1+1+1+3) + 1]
[ (1 +1+3+1) + 1]
[ (1+3+1+1) + 1]
[ (3+1+1+1) + 1]
[ (3+3) + 1]
[ (1+5 ) + 1]
[ (5+1) + 1]
2) Ajout de 3 à toutes les combinaisons possibles d'état (n = 4) ;
Ex : [(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]
3) Ajouter 5 à toutes les combinaisons possibles d'état(n = 2)
Ex : [ (1+1) + 5]
(Notez qu'il suffit d'ajouter uniquement du côté droit - tous les cas d'ajout depuis le côté gauche sont couverts, soit dans le même état, soit dans un autre, par exemple [ 1+(1+1+1+3)] n'est pas nécessaire dans l'état (n=6) car il est couvert par l'état (n = 4) [(1+1+1+1) + 3])
Maintenant, réfléchissez bien et assurez-vous que les trois cas ci-dessus couvrent toutes les manières possibles de former une somme totale de 7 ;
Par conséquent, nous pouvons dire que le résultat pour
état (7) = état (6) + état (4) + état (2)
ou
état (7) = état (7-1) + état (7-3) + état (7 -5)
En général,
état = état(n-1) + état(n-3) + état(n-5)
Ainsi, notre code ressemblera à :
int solve(int n){ // base case if (n < 0) return 0; if (n == 0) return 1; return solve(n-1) + solve(n-3) + solve(n-5);} Complexité temporelle : O(3^n)
Comme à chaque étape nous devons prendre trois décisions et la hauteur de l'arbre sera de l'ordre de n.
Espace auxiliaire : O
L'espace supplémentaire est utilisé en raison de la pile d'appels récursifs.
Le code ci-dessus semble exponentiel car il calcule encore et encore le même état. Donc, nous avons juste besoin d'ajouter la mémorisation.
Étape 4 : Ajouter une mémorisation ou une tabulation pour l'état
C'est la partie la plus simple d'une solution de programmation dynamique. Nous avons juste besoin de stocker la réponse d'état afin que la prochaine fois que cet état soit requis, nous puissions l'utiliser directement à partir de notre mémoire
Ajout de la mémorisation au code ci-dessus
int dp[MAXN];// this function returns the number of// arrangements to form 'n'int solve(int n){ // base case if (n < 0) return 0; if (n == 0) return 1; // checking if already calculated if (dp[n]!=-1) return dp[n]; // storing the result and returning return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);}Complexité temporelle : O
Comme nous avons juste besoin de faire des appels de fonction 3n et il n'y aura pas de calculs répétitifs car nous renvoyons des résultats précédemment calculés.
Espace auxiliaire : O