Programmation dynamique :exemples, problèmes courants et solutions

Il ne fait aucun doute que les problèmes de programmation dynamique peuvent être très intimidants lors d'un entretien de codage. Même lorsque vous savez qu'un problème doit être résolu à l'aide d'une méthode de programmation dynamique, il est difficile de trouver une solution qui fonctionne dans un laps de temps limité.

La meilleure façon d'être bon dans les problèmes de programmation dynamique est d'en parcourir autant que possible. Bien que vous n'ayez pas nécessairement besoin de mémoriser la solution à chaque problème, il est bon d'avoir une idée de la façon de la mettre en œuvre.

Qu'est-ce que la programmation dynamique ?

En termes simples, la programmation dynamique est une méthode d'optimisation des algorithmes récursifs, dont la plupart sont utilisés pour résoudre des problèmes informatiques ou mathématiques.

Vous pouvez également appeler cela une technique algorithmique pour résoudre un problème d'optimisation en le décomposant en sous-problèmes plus simples. Un principe clé sur lequel repose la programmation dynamique est que la solution optimale à un problème dépend des solutions à ses sous-problèmes.

Partout où nous voyons une solution récursive qui a des appels répétés pour les mêmes entrées, nous pouvons l'optimiser en utilisant la programmation dynamique. L'idée est de stocker simplement les résultats des sous-problèmes afin de ne pas avoir à les recalculer ultérieurement en cas de besoin.

Les solutions programmées dynamiquement ont une complexité polynomiale qui assure un temps d'exécution beaucoup plus rapide que d'autres techniques comme la récursivité ou le retour en arrière. Dans la plupart des cas, la programmation dynamique réduit les complexités temporelles, également appelées big-O, d'exponentielle à polynomiale.

Maintenant que vous avez une bonne idée de ce qu'est la programmation dynamique, il est temps de découvrir quelques problèmes courants et leurs solutions.

Problèmes de programmation dynamique

1. Problème de sac à dos

Énoncé du problème

Étant donné un ensemble d'éléments, chacun avec un poids et une valeur, déterminez le nombre de chaque élément à inclure dans une collection afin que le poids total ne dépasse pas une limite donnée et que la valeur totale soit aussi grande que possible.

On vous donne deux tableaux d'entiers values[0..n-1] et pondérations[0..n-1] qui représentent respectivement les valeurs et les poids associés à n éléments. Est également donné un entier W qui représente la capacité du sac à dos.

Ici, nous résolvons le problème du sac à dos 0/1, ce qui signifie que nous pouvons choisir d'ajouter un article ou de l'exclure.

Algorithme

• Créer un tableau à deux dimensions avec n+1 lignes et w+1 Colonnes. Un numéro de ligne n désigne l'ensemble des éléments de 1 à i , et un numéro de colonne w désigne la capacité de charge maximale du sac.
• La valeur numérique à [i][j] indique la valeur totale des articles jusqu'à i dans un sac pouvant supporter un poids maximum de j.
• À chaque coordonnée [i][j] dans le tableau, choisissez la valeur maximale que nous pouvons obtenir sans item i , soit la valeur maximale que l'on peut obtenir avec item i ---celui qui est le plus grand.
•  La valeur maximale pouvant être obtenue en incluant l'élément i correspond à la somme de l'élément i lui-même et la valeur maximale pouvant être obtenue avec la capacité restante du sac à dos.
• Effectuez cette étape jusqu'à ce que vous trouviez la valeur maximale pour le W ^ème ligne.

Code

def FindMax(W, n, valeurs, poids) :
 MaxVals =[[0 pour x dans la plage (W + 1)] pour x dans la plage (n + 1)] 
 
 pour i dans la plage (n + 1):
 pour w dans la plage (W + 1):
 si je ==0 ou w ==0 :
 MaxVals[i][w] =0 
 poids elif[i-1] <=w :
 MaxVals[i][w] =max(values[i-1] 
 + MaxVals[i-1][w-weights[i-1]], 
 MaxVals[i-1][w]) 
 autre:
 MaxVals[i][w] =MaxVals[i-1][w] 
 
 renvoie MaxVals[n][W] 
  

2. Problème de changement de pièces

Énoncé du problème

Supposons qu'on vous donne un tableau de nombres qui représentent les valeurs de chaque pièce. Étant donné un montant spécifique, trouvez le nombre minimum de pièces nécessaires pour gagner ce montant.

Algorithme

• Initialiser un tableau de taille n+1 , où n est le montant. Initialiser la valeur de chaque index i dans le tableau pour être égal au montant. Cela indique le nombre maximum de pièces (en utilisant des pièces de valeur nominale 1) nécessaires pour constituer ce montant.
• Puisqu'il n'y a pas de dénomination pour 0, initialisez le cas de base où array[0] =0 .
• Pour tout autre index i , nous comparons la valeur qu'il contient (qui est initialement définie sur n+1 ) avec la valeur array[i-k] +1 , où k est inférieur à i . Cela vérifie essentiellement l'ensemble du tableau jusqu'à i-1 pour trouver le nombre minimum possible de pièces que nous pouvons utiliser.
• Si la valeur de n'importe quel array[i-k] + 1 est inférieur à la valeur existante sur array[i] , remplacez la valeur à array[i] avec celui à array[i-k] +1 .

Code

def coin_change(d, montant, k) :
 nombres =[0]*(montant+1) 
 
 pour j dans la plage (1, montant + 1):
 minimum =montant 
 pour i dans la plage (1, k + 1):
 si(j>=d[i]):
 minimum =min(minimum, 1 + nombres[j-d[i]]) 
 nombres[j] =minimum 
 
 nombres de retour [montant] 
  

3. Fibonacci

Énoncé du problème

La série de Fibonacci est une séquence d'entiers où le prochain entier de la série est la somme des deux précédents.

Il est défini par la relation récursive suivante :F(0) =0, F(n) =F(n-1) + F(n-2) , où F(n) est le n ^ième terme. Dans ce problème, nous devons générer tous les nombres d'une suite de Fibonacci jusqu'à un n ^ème  donné terme.

Algorithme

• Tout d'abord, utilisez une approche récursive pour implémenter la relation de récurrence donnée.
• La résolution récursive de ce problème implique de décomposer F(n) en F(n-1) + F(n-2) , puis en appelant la fonction avec F(n-1) et F(n+2) comme paramètres. Nous faisons cela jusqu'aux cas de base où n =0 , ou n =1 sont atteints.
• Maintenant, nous utilisons une technique appelée mémorisation. Stockez les résultats de tous les appels de fonction dans un tableau. Cela garantira que pour chaque n, F(n) ne doit être calculé qu'une seule fois.
• Pour tout calcul ultérieur, sa valeur peut simplement être extraite du tableau en temps constant.

Code

def fibonacci(n) :
 fibNums =[0, 1] 
 pour i dans la plage (2, n + 1):
 fibNums.append(fibNums[i-1] + fibNums[i-2]) 
 retourner fibNums[n]  

4. Sous-séquence croissante la plus longue

Énoncé du problème

Trouver la longueur de la plus longue sous-séquence croissante à l'intérieur d'un tableau donné. La sous-séquence croissante la plus longue est une sous-séquence dans un tableau de nombres avec un ordre croissant. Les nombres dans la sous-séquence doivent être uniques et en ordre croissant.

De plus, les éléments de la séquence n'ont pas besoin d'être consécutifs.

Algorithme

• Commencez par une approche récursive où vous calculez la valeur de la plus longue sous-séquence croissante de chaque sous-tableau possible de l'index zéro à l'index i, où i est inférieur ou égal à la taille du tableau.
• Pour transformer cette méthode en une méthode dynamique, créez un tableau pour stocker la valeur de chaque sous-séquence. Initialise toutes les valeurs de ce tableau à 0.
• Chaque index i  de ce tableau correspond à la longueur de la plus longue sous-séquence croissante pour un sous-tableau de taille i .
• Maintenant, pour chaque appel récursif de findLIS(arr, n) , vérifiez le n ^ème indice du tableau. Si cette valeur est 0, calculez-la à l'aide de la méthode de la première étape et stockez-la au niveau n. ^ème indice.
• Enfin, renvoyez la valeur maximale du tableau. C'est la longueur de la plus longue sous-séquence croissante d'une taille donnée n .

Code

def findLIS(myArray) :
 n =len(monTableau) 
 lis =[0]*n 
 
 pour i dans l'intervalle (1 , n):
 pour j dans la plage (0 , i):
 si monTableau[i]> monTableau[j] et lis[i] lis[i] =lis[j]+1 
 
 maxVal=0 
 pour i dans la plage (n):
 maxVal =max(maxVal , lis[i]) 
 
 retourner maxVal 

Solutions aux problèmes de programmation dynamique

Maintenant que vous avez traversé certains des problèmes de programmation dynamique les plus populaires, il est temps d'essayer de mettre en œuvre les solutions par vous-même. Si vous êtes bloqué, vous pouvez toujours revenir et vous référer à la section algorithme pour chaque problème ci-dessus.

Compte tenu de la popularité actuelle des techniques telles que la récursivité et la programmation dynamique, il ne sera pas inutile de consulter certaines plates-formes populaires sur lesquelles vous pourrez apprendre de tels concepts et perfectionner vos compétences en codage. Bien que vous ne rencontriez peut-être pas ces problèmes au quotidien, vous les rencontrerez sûrement lors d'un entretien technique.

Naturellement, avoir le savoir-faire des problèmes courants rapportera forcément des dividendes lors de votre prochaine entrevue. Alors ouvrez votre IDE préféré et lancez-vous !