Il ne fait aucun doute que les problèmes de programmation dynamique peuvent être très intimidants lors d'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 de travail enun laps de temps limité.

publicité

La meilleure façon de maîtriser les problèmes de programmation dynamique est d'en traiter 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 procéder.mettre en œuvre un.

Qu'est-ce que la programmation dynamique?

En termes simples, la programmation dynamique est une méthode d'optimisation pour les 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 la programmation dynamique est basée 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 de ne pas avoir à les recalculer en cas de besoin plus tard.

publicité

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 arrière. Dans la plupart des cas, la programmation dynamique réduit les complexités temporelles, également appelées grand-O , de l'exponentielle au polynôme.

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'articles, chacun avec un poids et une valeur, déterminez le nombre de chaque article à 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 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.

publicité

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 indique 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 élément i ou la valeur maximale que nous pouvons obtenir avec élément i --- selon la valeur la plus élevée.
  • La valeur maximale pouvant être obtenue en incluant l'élément i est la somme de l'élément i elle-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 th ligne.
publicité

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] [w-poids [i-1]],
MaxVals [i-1] [w]
sinon :
MaxVals [i] [w] = MaxVals [i-1] [w]

retourne MaxVals [n] [W]

2. Problème de changement de pièce

Énoncé du problème

Supposons que l'on vous donne 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 obtenir ce montant.

Algorithme

  • Initialiser un tableau de taille n + 1 , où n est le montant. Initialise la valeur de chaque indice i 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 i , nous comparons la valeur qu'il contient qui est initialement définie sur n + 1 avec la valeur tableau [ik] +1 , où k est inférieur à i . 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 est quelconque tableau [ik] + 1 est inférieur à la valeur existante à tableau [i] , remplacez la valeur à tableau [i] avec celui à tableau [ik] +1 .
publicité

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 [jd [i]]
nombres [j] = minimum

renvoyer les numéros [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 th terme. Dans ce problème, nous devons générer tous les nombres dans une séquence de Fibonacci jusqu'à un n donné th 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 une panne F n dans F n-1 + F n-2 , puis en appelant la fonction avec F n-1 et F n + 2 en tant que paramètres. Nous faisons cela jusqu'aux cas de base où n = 0 ou n = 1 sont atteints.
  • Nous utilisons maintenant 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.
publicité

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 dans 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 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. Initialisez toutes les valeurs de ce tableau à 0.
  • chaque index i de ce tableau correspond à la longueur de la sous-séquence croissante la plus longue pour un sous-tableau de taille i .
  • Maintenant, pour chaque appel récursif de findLIS arr, n , vérifiez le n th index du tableau. Si cette valeur est égale à 0, calculez la valeur à l'aide de la méthode de la première étape et stockez-la dans le n th index.
  • Enfin, renvoie la valeur maximale du tableau. C'est la longueur de la sous-séquence croissante la plus longue d'une taille donnée n .
publicité

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 traversé certains des problèmes de programmation dynamique les plus courants, il est temps d'essayer d'implémenter 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 fera pas de mal de consulter certaines plates-formes populaires où vous pouvez apprendre ces concepts et perfectionnez vos compétences en codage . Bien que vous ne rencontriez pas ces problèmes quotidiennement, vous les rencontrerez sûrement lors d'un entretien technique.

publicité

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

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.

À propos de l'auteur
publicité