Programmation dynamique: exemples, problèmes courants et solutions

Hibou Gourou

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. 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 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 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 de ne pas avoir à 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 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'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 valeurs de tableaux d'entiers [0..n-1] et des poids [0..n-1] qui représentent respectivement les valeurs et les poids associés à n éléments. On donne également 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éez un tableau à deux dimensions avec n + 1 lignes et w + 1 colonnes. Un numéro de ligne n désigne l'ensemble d'articles 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 porter un poids maximum de j.
  • À chaque coordonnée [i] [j] du tableau, choisissez la valeur maximale que nous pouvons obtenir sans l' élément i , ou la valeur maximale que nous pouvons obtenir avec l' élément i — selon la plus grande des deux.
  • La valeur maximale pouvant être obtenue en incluant l'élément i est la somme de l'élément i lui-même et de 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 la W ème ligne.

Code

 def FindMax(W, n, values, weights):
 MaxVals = [[0 for x in range(W + 1)] for x in range(n + 1)]

 for i in range(n + 1):
 for w in range(W + 1):
 if i == 0 or w == 0:
 MaxVals[i][w] = 0
 elif weights[i-1] <= w:
 MaxVals[i][w] = max(values[i-1]
 + MaxVals[i-1][w-weights[i-1]],
 MaxVals[i-1][w])
 else:
 MaxVals[i][w] = MaxVals[i-1][w]

 return 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 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 faire ce montant.

Algorithme

  • Initialisez un tableau de taille n + 1 , où n est le montant. Initialisez la valeur de chaque index i dans le tableau pour qu'elle soit égale 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 chaque autre indice i , nous comparons la valeur qu'il contient (qui est initialement fixée à n + 1 ) avec le tableau de valeurs [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 d'un tableau [ik] + 1 est inférieure à la valeur existante du tableau [i] , remplacez la valeur du tableau [i] par celle du tableau [ik] +1 .

Code

 def coin_change(d, amount, k):
 numbers = [0]*(amount+1)

 for j in range(1, amount+1):
 minimum = amount
 for i in range(1, k+1):
 if(j >= d[i]):
 minimum = min(minimum, 1 + numbers[jd[i]])
 numbers[j] = minimum

 return numbers[amount]

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 ème terme. Dans ce problème, nous devons générer tous les nombres dans une séquence de Fibonacci jusqu'à un n ème terme donné.

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 consiste à décomposer F (n) en F (n-1) + F (n-2) , puis à appeler la fonction avec F (n-1) et F (n + 2) comme paramètres. Nous faisons cela jusqu'à ce que les cas de base où n = 0 ou n = 1 soient 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 tous les calculs ultérieurs, sa valeur peut simplement être extraite du tableau en temps constant.

Code

 def fibonacci(n):
 fibNums = [0, 1]
 for i in range(2, n+1):
 fibNums.append(fibNums[i-1] + fibNums[i-2])
 return 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 par 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 sous-séquence croissante la plus longue 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 indice 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 ième index du tableau. Si cette valeur est 0, calculez la valeur à l'aide de la méthode de la première étape et stockez-la au n ième index.
  • Enfin, renvoyez la valeur maximale du tableau. C'est la longueur de la sous-séquence croissante la plus longue d'une taille n donnée.

Code

 def findLIS(myArray):
 n = len(myArray)
 lis = [0]*n

 for i in range (1 , n):
 for j in range(0 , i):
 if myArray[i] > myArray[j] and lis[i]< lis[j] + 1 :
 lis[i] = lis[j]+1

 maxVal= 0
 for i in range(n):
 maxVal = max(maxVal , lis[i])

 return 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 de tels concepts et perfectionner 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!