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 dans une interview de codage. Même si 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 fonctionnelle dans un laps de temps limité.

La meilleure façon de maîtriser les problèmes de programmation dynamique est d'en traiter autant que possible. Même si vous n’avez pas nécessairement besoin de mémoriser la solution à chaque problème, il est bon d’avoir une idée de la façon d’en mettre en œuvre une.

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 l'appeler 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 à l'aide de la programmation dynamique. L'idée est de simplement stocker les résultats des sous-problèmes afin que nous n'ayons pas à les recalculer en cas de besoin plus tard.

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 grand-O, d'exponentielle à polynomiale.

Qu'est-ce que la notation Big-O?

Votre code doit être efficace, mais comment montrer à quel point quelque chose est efficace? Avec Big-O!

Maintenant que vous avez une bonne idée de ce qu’est la programmation dynamique, il est temps d’examiner 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'articles, chacun avec un poids et une valeur, déterminez le nombre de chaque article à inclure dans un collection afin que le poids total ne dépasse pas une limite donnée et que la valeur totale soit aussi grande que possible.

Vous disposez de deux tableaux d'entiers valeurs [0..n-1] et poids [0..n-1] qui représentent respectivement les valeurs et les poids associés à n éléments. Un entier est également donné 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éez 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 à jeet un numéro de colonne w désigne la capacité de charge maximale du sac.
• La valeur numérique à [i] [j] désigne la valeur totale des articles jusqu'à je 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 élément i, ou la valeur maximale que nous pouvons obtenir avec élément icelui qui est le plus grand.
• La valeur maximale pouvant être obtenue en incluant l'élément i est la somme de l'élément je lui-même et la valeur maximale qui peut être obtenue avec la capacité restante du sac à dos.
• Effectuez cette étape jusqu'à ce que vous trouviez la valeur maximale pour le W^e rangée.

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 i == 0 ou w == 0:
MaxVals [i] [w] = 0
poids elif [i-1] <= w:
MaxVals [i] [w] = max (valeurs [i-1]
+ MaxVals [i-1] [poids w [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èce

Énoncé du problème

Supposons que vous receviez un tableau de nombres représentant les valeurs de chaque pièce. Étant donné un montant spécifique, trouvez le nombre minimum de pièces nécessaires pour faire ce montant.

Algorithme

• Initialiser un tableau de taille n + 1, où n est le montant. Initialiser la valeur de chaque index je dans le tableau pour être égal au montant. Cela indique le nombre maximum de pièces (en utilisant des pièces de dénomination 1) nécessaires pour constituer ce montant.
• Puisqu'il n'y a pas de dénomination pour 0, initialisez le cas de base où tableau [0] = 0.
• Pour tous les autres index je, nous y comparons la valeur (qui est initialement fixée à n + 1) avec la valeur tableau [i-k] +1, où k est inférieur à je. Cela vérifie essentiellement l'ensemble du tableau jusqu'à i-1 pour trouver le nombre minimum de pièces que nous pouvons utiliser.
• Si la valeur à un tableau [i-k] + 1 est inférieure à la valeur existante à tableau [i], remplacez la valeur à tableau [i] avec celui de tableau [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
numéros 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 alors^e terme. Dans ce problème, nous devons générer tous les nombres dans une séquence de Fibonacci jusqu'à un n donné^e 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 la décomposition F (n) dans 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 récupérée 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])
retourne fibNums [n] 

4. Sous-séquence croissante la plus longue

Énoncé du problème

Trouvez la longueur de la sous-séquence croissante la plus longue à 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 dans l'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 tous les sous-tableaux possibles de l'index zéro à l'index i, où i est inférieur ou égal à la taille du déployer.
• Pour transformer cette méthode en une méthode dynamique, créez un tableau pour stocker la valeur de chaque sous-séquence. Initialisez toutes les valeurs de ce tableau à 0.
• Chaque index je de ce tableau correspond à la longueur de la plus longue sous-séquence croissante pour un sous-tableau de taille je.
• Maintenant, pour chaque appel récursif de findLIS (arr, n), vérifier la n^e index du tableau. Si cette valeur est égale à 0, calculez la valeur à l'aide de la méthode de la première étape et enregistrez-la au n^e 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 (myArray)
lis = [0] * n
pour i dans la plage (1, n):
pour j dans la plage (0, i):
si myArray [i]> myArray [j] et lis [i] lis [i] = lis [j] +1
maxVal = 0
pour i dans la plage (n):
maxVal = max (maxVal, lis [i])
retour maxVal

Solutions aux problèmes de programmation dynamique

Maintenant que vous avez rencontré certains des problèmes de programmation dynamique les plus courants, 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.

Étant donné 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 pouvez apprendre ces concepts perfectionnez vos compétences en codage. Bien que vous ne rencontriez peut-être pas ces problèmes quotidiennement, vous les rencontrerez sûrement lors d'un entretien technique.

Naturellement, avoir le savoir-faire des problèmes communs est lié à payer des dividendes lors de votre prochain entretien. Alors ouvrez votre IDE préféré, et lancez-vous!

Les 9 meilleures chaînes YouTube avec code pour apprendre la programmation

Prêt à commencer à coder? Ces chaînes YouTube sont un excellent moyen de se lancer dans le développement de jeux, d'applications, Web et autres.

A propos de l'auteur