16 Exercices Corrigés Programmation dynamique et Diviser pour régner

Cette page propose plusieurs exercices corrigés de programmation dynamique et diviser pour régner.  L’objectif est de comprendre la différence entre le paradigme Divide & Conquer (Diviser pour régner) et la programmation dynamique. Les spécificités de la recherche de chemin (plus court chemin), problème de planification, problème de flot maximum et plus généralement la théorie des graphes est traitée à part.

Diviser pour régner et la programmation dynamique

Exercice 1

Écrivez un pseudo-code pour un algorithme de type diviser pour régner permettant de trouver la position du plus grand élément dans un tableau de nombres. Écrivez un pseudo-code pour un algorithme de force brute, comparez avec le précédent. Montrez un arbre du processus de l’algorithme diviser pour mieux régner. Quel est le niveau maximal de l’arborescence pour les nombres ?

diviser pour régner programmation dynamique exercices corrigés

L’algorithme de force brute est trivial : une boucle.

A chaque niveau l, l’arbre binaire complet est composé de 2^(l-1) feuille. Donc le total des sommets est 2^l -1. Soit l le niveau de l’arbre, donc l=sup(log_2 (n)).

Exercice 2

On vous donne un tableau avec des entiers (positif, négatif, zéro) et vous êtes censé trouver la somme contiguë maximale dans ce tableau. Par conséquent, vous devez trouver un sous-tableau qui donne la plus grande somme. Exemple, si le tableau donné est : 5, -6, 7, 12, -3, 0, -11, -6

Supposons que votre tableau d’entrée s’appelle A. Ce que vous devez faire est de former un autre tableau, disons B, dont chaque valeur i est calculée en utilisant la formule récursive, max(A[i], B[i-1]+A[i ])

Ce que vous faites effectivement, c’est que vous choisissez d’étendre la fenêtre précédente ou d’en démarrer une nouvelle. Vous pouvez le faire puisque vous n’êtes censé sélectionner que des éléments continus dans le cadre de vos sous-ensembles.

5, -6, 7, 12, -3, 0, -11, -6

La réponse serait 19 (du sous-tableau {7,12} )

Exercice 3

Utilisez la sous-chaîne commune la plus longue pour : BDCABA et ABCBDAB. L’algorithme est décrit comme suit:

diviser pour régner programmation dynamique exercices corrigés sous-chaîne commune

Exercice 4

Adaptez la sous-chaîne commune la plus longue à la sous-séquence commune la plus longue : BDCABA et ABCBDAB. Le problème de la plus longue sous-séquence commune (LCS) consiste à trouver la plus longue sous-séquence commune à toutes les séquences d’un ensemble de séquences (souvent seulement deux séquences).

Cela diffère des problèmes de recherche de sous-chaînes communes : contrairement aux sous-chaînes, les sous-séquences ne sont pas obligées d’occuper des positions consécutives dans les séquences d’origine.

Exercice 5

La distance de Levenshtein est une métrique de chaîne permettant de mesurer la différence entre deux séquences. De manière informelle, la distance de Levenshtein entre deux mots est le nombre minimum de modifications d’un seul caractère (c’est-à-dire des insertions, des suppressions ou des substitutions) nécessaires pour changer un mot en l’autre. Proposer un programme dynamique pour résoudre ce problème. Essai avec MEILENSTEIN et LEVENSHTEIN.

Exercice 6

Alice et Bob jouent à tour de rôle à un jeu, Alice commençant en premier.

Initialement, il y a un nombre n au tableau. Au tour de chaque joueur, ce joueur effectue un coup consistant en :

Choisir n’importe quel x avec 0 < x < n et n % x == 0.
Remplacer le nombre n au tableau par n – x.
De plus, si un joueur ne peut pas bouger, il perd la partie.

Renvoyer vrai si et seulement si Alice gagne la partie, en supposant que les deux joueurs jouent de manière optimale.

Exemple 1:

Entrée : n = 2
Sortie : vrai
Explication : Alice choisit 1 et Bob n’a plus de coups.

Exemple 2 :

Entrée : n = 3
Sortie : faux
Explication : Alice choisit 1, Bob choisit 1 et Alice n’a plus de coups.

Pour répondre à ce problème, nous allons construire un tableau de solution. dp[i] indique le résultat du jeu pour le nombre donné i et pour le joueur qui a commencé la partie. Alice essaiera tous les facteurs et choisira celui qui donne à son adversaire une valeur perdante.

divisor game

Il est aussi possible de résoudre ce problème de manière récursive plus classique, appelé Top-Down.

divisor game

Et pour un côté plus pratique nous allons ajouter une mémoïsation.

divisor game

Exercice 7

On vous donne un coût de tableau d’entiers où coût[i] est le coût de la ième marche d’un escalier. Une fois que vous avez payé le coût, vous pouvez monter une ou deux marches.

Vous pouvez soit démarrer à partir de l’étape avec l’indice 0, soit à partir de l’étape avec l’indice 1.

Renvoyez le coût minimum pour atteindre le sommet de l’étage.

Exemple 1:

Entrée : coût = [10,15,20]
Sortie : 15

Explication : Vous commencerez à l’index 1.
– Payez 15 et montez deux marches pour atteindre le sommet.
Le coût total est de 15.

Exemple 2 :

Entrée : coût = [1,100,1,1,1,100,1,1,100,1]
Sortie : 6

Explication : Vous commencerez à l’index 0.
– Payez 1 et montez deux marches pour atteindre l’indice 2.
– Payez 1 et montez deux marches pour atteindre l’indice 4.
– Payez 1 et montez deux marches pour atteindre l’indice 6.
– Payez 1 et montez d’une marche pour atteindre l’indice 7.
– Payez 1 et montez deux marches pour atteindre l’indice 9.
– Payez 1 et montez une marche pour atteindre le sommet.
Le coût total est de 6.

Pour un premier jet, nous allons résoudre ce problème en récursif. Pour cela nous gardons en mémoire le plus petit coût en considérant que l’on fasse marche arrière d’une marche et de deux marches. Et ainsi de suite jusqu’à avoir le coût de la première ou deuxième marche.

mincost(0) = cost[0]
mincost(1) = cost[1]

mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))

Ce qui donne le code suivant :

climbing stairs

Dans un second temps, nous allons rester en approche top-down et ajouter un système de mémoïsation. Ainsi, un minCost déjà trouver ne sera pas recalculer par la suite.

climbing stairs

Enfin, nous allons prendre le problème en bottom-up pour faire de la programmation dynamique;

climbing stairs

Exercice 8

Alice et Bob jouent à un jeu avec des tas de pierres. Il y a un nombre pair de piles disposées dans une rangée, et chaque pile a un nombre entier positif de piles de pierres[i].

L’objectif du jeu est de terminer avec le plus de pierres. Le nombre total de pierres sur toutes les piles est impair, il n’y a donc pas d’égalité.

Alice et Bob se relaient, Alice commençant en premier. A chaque tour, un joueur prend toute la pile de pierres soit depuis le début soit depuis la fin de la rangée. Cela continue jusqu’à ce qu’il n’y ait plus de piles, à quel point la personne avec le plus de pierres gagne.

En supposant qu’Alice et Bob jouent de manière optimale, renvoyez true si Alice gagne la partie, ou false si Bob gagne.

Entrée : pierres = [5,3,4,5]
Sortie : vrai

Alice commence en premier et ne peut prendre que les 5 premiers ou les 5 derniers.
Disons qu’elle prend les 5 premiers, de sorte que la ligne devient [3, 4, 5].
Si Bob prend 3, alors le tableau est [4, 5], et Alice prend 5 pour gagner avec 10 points.
Si Bob prend les 5 derniers, alors le tableau est [3, 4], et Alice prend 4 pour gagner avec 9 points.

Cela a démontré que prendre les 5 premiers était un coup gagnant pour Alice, nous retournons donc vrai.

Commençons par une approche top-down avec mémoïsation.

  • Veuillez noter que les deux joueurs jouent de manière optimale, nous jouons donc de manière optimale, peu importe qui est Alice, qui est Bob.
  • Soit dp(left, right) return [firstScore, secondScore] où firstScore est le score maximum lorsque le joueur1 joue en premier, secondScore est le score maximum lorsque le joueur2 joue en second, il ramasse des pierres en piles[left]…piles[right ].
  • Pour les pierres en tas[left]…piles[right], il y a 2 choix pour le joueur1 à choisir :
    • Choisissez à gauche : pickLeft = dp(gauche + 1, droite).
      • Le score du joueur1 = piles[left] + le score du deuxième choix de pickLeft, donc firstScore = piles[left] + pickLeft[1]
      • Le score du joueur2 = score du premier choix de pickLeft, donc secondScore = pickLeft[0]
    • Choisir à droite : pickRight = dp(gauche, droite – 1).
      • Le score du joueur1 = piles[right] + le deuxième score de pickRight, donc firstScore = piles[right] + pickRight[1]
      • Le score du joueur2 = score du premier choix de pickRight, donc secondScore = pickRight[0].
  • Nous devons obtenir le score maximum lorsque le joueur 1 joue en premier parmi plus de 2 choix.
  • Enfin, dp(0, len(piles) – 1) return [firstScore, secondScore], où alexScore = firstScore puisque Alice joue en premier, leeScore = secondScore puisque Bob joue en second.

stone game

Maintenant on va faire un algorithme en bottom-up en gardant la mémoïsation. Ainsi l’algorithme sera en programmation dynamique.

stone game

Exercice 9

Il y a n soldats debout en ligne. Chaque soldat se voit attribuer une valeur de classement unique.

Vous devez former une équipe de 3 soldats parmi eux selon les règles suivantes :

Choisissez 3 soldats avec l’indice (i, j, k) avec le classement (classement[i], classement[j], classement[k]).
Une équipe est valide si : (rating[i] < rating[j] < rating[k]) ou (rating[i] > rating[j] > rating[k]) où (0 <= i < j < k < n).
Renvoyez le nombre d’équipes que vous pouvez former compte tenu des conditions. (les soldats peuvent faire partie de plusieurs équipes).

Exemple 1:

Entrée : note = [2,5,3,4,1]
Sortie : 3
Explication : On peut former trois équipes compte tenu des conditions. (2,3,4), (5,4,1), (5,3,1).

Exemple 2 :

Entrée : note = [2,1,3]
Sortie : 0
Explication : Nous ne pouvons former aucune équipe compte tenu des conditions.

Il est facile de faire un algorithme glouton. Ce dernier est en O(n^3) donc on va essayer d’améliorer la complexité avec de la programmation dynamique.

nombre équipe programmation dynamique

Voici l’idée principale dans la version programmation dynamique :

Premièrement, nous calculons ce cas note[i] > note[j] > note[k] étant donné que i > j > k. Ensuite, calculez le cas note[i] < note[j] < note[k].

Définir dp[i] : combien d’éléments dans la notation de 0 à i-1 sont inférieurs à la notation[i].

Pour chaque fois que nous avons trouvé note[i] > note[j], nous accumulons dp[j]. Ici, dp[j] signifie combien de notes[k] existent de 0 à j-1. C’est-à-dire, combien de cas satisfont la note[i] > la note[j] > la note[k].

nombre équipe programmation dynamique

Exercice 10

On vous donne un tableau de prix où prix[i] est le prix d’une action donnée le ième jour, et des frais entiers représentant des frais de transaction.

Trouvez le profit maximum que vous pouvez réaliser. Vous pouvez effectuer autant de transactions que vous le souhaitez, mais vous devez payer les frais de transaction pour chaque transaction.

Remarque : Vous ne pouvez pas vous engager dans plusieurs transactions simultanément (c’est-à-dire que vous devez vendre l’action avant d’acheter à nouveau).

Entrée : prix = [1,3,2,8,4,9], frais = 2
Sortie : 8

Explication : Le profit maximal peut être atteint en :
– Acheter à des prix [0] = 1
– Vendre à des prix[3] = 8
– Acheter à des prix [4] = 4
– Vendre à des prix[5] = 9

Le bénéfice total est ((8 – 1) – 2) + ((9 – 4) – 2) = 8.

Commençons dans un premier temps avec l’approche top-down.

  • Soit dp(i, canBuy) le profit maximum que nous pouvons tirer des prix[i..n-1] avec le drapeau canBuy == True signifie que nous pouvons acheter le ième jour.
  • Pour le ième jour nous avons 2 options :
    • Ignorez-le : profit = dp(i+1)
    • Achetez-le ou vendez-le
      • Si achat : profit = dp(i+1) – prix[i]
      • Si vente : profit = dp(i+1) + prix[i] – commission

achat vente programmation dynamique

On va convertir en une approche bottom-up pour faire de la programmation dynamique plus traditionnelle.

Soit dp[i][j] le profit maximum que nous pouvons tirer des prix[i..n-1] avec le drapeau j == 1 signifie que nous pouvons acheter le ième jour.

achat vente programmation dynamique

Puisque notre dp n’accède qu’à 2 états : l’état dp actuel dp, l’état dp précédent dpPrev. Nous pouvons optimiser à O(1) dans la complexité de l’espace.

achat vente programmation dynamique

Exercice 11

Vous avez prévu un voyage en train un an à l’avance. Les jours de l’année au cours desquels vous voyagerez sont donnés sous la forme d’un nombre entier de jours. Chaque jour est un entier compris entre 1 et 365.

Les billets de train sont vendus de trois manières différentes :

un pass 1 jour est vendu au prix de [0] dollars,
un laissez-passer de 7 jours est vendu pour des coûts [1] dollars, et
un laissez-passer de 30 jours est vendu pour des coûts [2] dollars.
Les laissez-passer permettent autant de jours de voyage consécutifs.

Par exemple, si nous obtenons un pass 7 jours le jour 2, nous pouvons voyager pendant 7 jours : 2, 3, 4, 5, 6, 7 et 8.
Renvoyez le nombre minimum de dollars dont vous avez besoin pour voyager chaque jour dans la liste de jours donnée.
Entrée : jours = [1,4,6,7,8,20], coûts = [2,7,15]
Sortie : 11

Par exemple, voici une façon d’acheter des laissez-passer qui vous permet de voyager selon votre plan de voyage :
Le jour 1, vous avez acheté un pass 1 jour pour un coût[0] = 2 $, qui couvrait le jour 1.
Le jour 3, vous avez acheté un pass de 7 jours pour un coût[1] = 7 $, qui couvrait les jours 3, 4, …, 9.
Le jour 20, vous avez acheté un pass d’un jour pour un coût[0] = 2 $, qui couvrait le jour 20.

Au total, vous avez dépensé 11 $ et couvert tous les jours de votre voyage.

Nous allons voir ici l’approche bottom-up car le raisonnement est très similaire au problème de sac-à-dos (knapsack) dans la construction de la solution.

dp[i] signifie jusqu’au ième jour le coût minimum des billets. La taille du tableau dp dépend du dernier jour de voyage, nous n’avons donc pas besoin d’une longueur de tableau de 365.

Nous avons besoin d’un tableau booléen pour marquer les jours de voyage, la raison en est que si ce n’est pas un jour de voyage, nous n’avons pas besoin de billet. Cependant, s’il s’agit d’un jour de voyage, nous envisageons trois scénarios (avec trois types de tickects) :

Si un ticket 1 jour le jour i, dp[i] = dp[i – 1] + coût[0]
Si un billet de 7 jours se termine le jour i, dp[i] = min(dp[i – 7], dp[i – 6] … dp[i – 1]) + coût[1]
Si un ticket de 30 jours se termine le jour i, dp[i] = min(dp[i – 30], dp[i – 29] … dp[i – 1]) + coût[2]

Mais puisque la valeur de dp array augmente, donc :
Pour un ticket 7 jours se terminant le jour i, dp[i] = dp[i – 7] + coût[1]
Pour un ticket 30 jours se terminant le jour i, dp[i] = dp[i – 30] + coût[2]

ticket programmation dynamique

Exercice 12

On vous donne un tableau de valeurs entières où values[i] représente la valeur du ième site touristique. Deux sites touristiques i et j ont une distance j – i entre eux.

Le score d’une paire (i < j) de sites touristiques est valeurs[i] + valeurs[j] + i – j : la somme des valeurs des sites touristiques, moins la distance qui les sépare.

Renvoie le score maximum d’une paire de sites touristiques.

Entrée : valeurs = [8,1,5,2,6]
Sortie : 11

Nous avons i = 0, j = 2, valeurs[i] + valeurs[j] + i – j = 8 + 5 + 0 – 2 = 11

Supposons que nous choisissions le site [i,…j]. La partition peut être décomposée en 2 parties.

La première partie est le startGain que vous gagnez en commençant à un certain point i. Notez que startGain[i] = a[i] + i.

La deuxième partie est le endGain qui est le montant que vous gagnez en terminant à un certain point j. Notez que endGain[i] = a[j] – j.

Notez que endGain peut être négatif.

Le gain global pour [i,…j] n’est rien d’autre que startGain[i] + endGain[j]. (Cela peut être facilement vérifié par les définitions).

Nous devons maximiser le gain global.

Quelles sont les positions possibles pour commencer le voyage ? Il est clair que nous pouvons tout commencer sauf le dernier élément. Ainsi, le voyage optimal doit commencer à l’un de ces éléments.

Supposons que nous ne soyons autorisés à commencer un voyage qu’à i. Quel est le montant maximum que nous pouvons gagner dans ce cas ? Eh bien, puisque le startGain est fixe, nous devons maximiser le endGain. Nous pouvons le faire en nous arrêtant à un élément qui a le maximum endGain à condition qu’il apparaisse à droite de i.

Comme indiqué ci-dessus, pour chaque i, nous devons trouver le endGain maximal à sa droite.

maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1]) = max(maxEndRight[i+1], a[i+1] – (i+1))

maxEndRight[i] représente le endGain le plus élevé que vous pouvez obtenir en vous arrêtant à n’importe quel point strictement à droite de i. Puisque par définition, nous connaissons déjà endGain[i+1] (le gain le plus élevé possible en terminant à n’importe quel point à droite de i+1), nous n’avons qu’à vérifier la possibilité de savoir si s’arrêter à i+1 serait bénéfique ou non. D’où la définition de DP.

Pour chaque i valide, overallGain[i] = startGain[i] + maxEndRight[i] = a[i] + i + maxEndRight[i]

Notez que maxEndRight[i] ne dépend que de maxEndRight[i+1]. Par conséquent, nous pouvons utiliser 2 variables pour suivre les valeurs précédentes.

Puisque nous avons besoin de la valeur de maxEndRight[i+1] pour calculer la valeur de maxEndRight[i], nous commençons donc les itérations à l’arrière.

Comme indiqué, les voyages ne peuvent pas commencer au dernier élément, donc la boucle for commence à i=n-2. Pour cette valeur, maxEndingRight est initialisé à endGain[lastIndex] car c’est le seul moyen possible de terminer le voyage.

exploration programmation dynamique

Exercice 13

Vous êtes un voleur professionnel qui envisage de cambrioler des maisons le long d’une rue. Chaque maison a une certaine somme d’argent cachée, la seule contrainte vous empêchant de cambrioler chacune d’elles est que les maisons adjacentes ont des systèmes de sécurité connectés et elle contactera automatiquement la police si deux maisons adjacentes ont été cambriolées la même nuit.

Étant donné un tableau d’entiers nums représentant le montant d’argent de chaque maison, renvoyez le montant d’argent maximum que vous pouvez voler ce soir sans alerter la police.

Entrée : nombres = [1,2,3,1]
Sortie : 4
Explication : Voler la maison 1 (argent = 1) puis voler la maison 3 (argent = 3).
Montant total que vous pouvez voler = 1 + 3 = 4.

Entrée : nombres = [2,7,9,3,1]
Sortie : 12
Explication : Voler la maison 1 (argent = 2), voler la maison 3 (argent = 9) et voler la maison 5 (argent = 1).
Montant total que vous pouvez voler = 2 + 9 + 1 = 12.

Trouvons une relation récursive.

Un voleur a 2 options : a) voler la maison actuelle i ; b) ne cambriolez pas la maison actuelle.

Si une option « a » est sélectionnée, cela signifie qu’elle ne peut pas voler la maison i-1 précédente, mais peut passer en toute sécurité à celle qui précède la i-2 précédente et obtient tout le butin cumulatif qui suit.

Si une option « b » est sélectionnée, le voleur obtient tout le butin possible du vol de i-1 et de tous les bâtiments suivants.

Cela revient donc à calculer ce qui est le plus rentable :

vol de la maison actuelle + pillage des maisons avant la précédente le butin du vol de maison précédent et tout butin capturé avant cela
rob(i) = Math.max( rob(i – 2) + currentHouseValue, rob(i – 1) )

Cela donnerait la version récursive suivante :

rob house recursive

Réfléchissons maintenant à une méthode utilisant la mémoïsation. Pour cela, nous allons considérer qu’à l’ajout de chaque maison (donc à l’étape i, soit on ne vole pas cette maison (donc même valeur que l’étape i-1), soit on vole la maison et donc potentiellement celle en i-2.

Nous prenons donc le maximum entre l’optimum en l’étape i-1 et en i-2 + valeur de la nouvelle maison. Pour rappel, chaque étape est optimal car résoudre le problème avec sans la nouvelle maison est optimale par principe de sous-problème.

Ce qui donne :

rob house memoization

On est ici sur une complexité en mémoire et en temps en O(n).

Transformons ce code est bottom-up, donc en programmation dynamique :

rob house programmation dynamique

Notons que comme Fibonacci nous n’avons pas besoin de garder l’ensemble des valeurs précédentes car le sous-problème optimale en i-1 et i-2 ne change pas quelque soit la nouvelle maison. Notez que cette optimisation ne permettra pas de savoir quelles maisons ont été choisies !

rob house programmation dynamique

La complexité en espace est O(1).

Exercice 14

On vous donne k oeufs identiques et vous avez accès à un bâtiment de n étages numérotés de 1 à n.

Vous savez qu’il existe un étage f où 0 <= f <= n tel que tout œuf tombé à un étage supérieur à f se cassera, et tout œuf tombé à ou en dessous de l’étage f ne se cassera pas.

À chaque mouvement, vous pouvez prendre un œuf non cassé et le faire tomber de n’importe quel étage x (où 1 <= x <= n). Si l’œuf se casse, vous ne pouvez plus l’utiliser. Cependant, si l’œuf ne se casse pas, vous pouvez le réutiliser lors de futurs mouvements.

Renvoie le nombre minimum de mouvements dont vous avez besoin pour déterminer avec certitude quelle est la valeur de f.

Entrée : k = 1, n = 2
Sortie : 2

Déposez l’œuf de l’étage 1. S’il se casse, nous savons que f = 0.

Sinon, laissez tomber l’œuf de l’étage 2. S’il se casse, nous savons que f = 1.
S’il ne casse pas, alors nous savons f = 2.

Par conséquent, nous avons besoin d’au moins 2 mouvements pour déterminer avec certitude quelle est la valeur de f.

Tout d’abord, nous pouvons voir que pour obtenir la réponse d’étages et d’œufs plus grands, les résultats de cas plus petits sont utiles pour l’analyse, ce qui conduit à une programmation dynamique.

Ensuite, comment définir un état pour chaque lâché afin d’obtenir le plancher optimal ? Ici nous avons deux variables :

Le nombre d’œufs restant à jeter i, (0 <= i <= K)
Le nombre d’étages restant pour tester j, (1 <= j <= N)

La réponse (les plus petits temps pour obtenir le plancher optimal) peut être la valeur de chaque état dp.

Le cas de base est plutôt intuitif à trouver. Pensez aux cas avec des œufs et des planchers les plus petits :

dp[1][j] = j, j = 1…N # un œuf, vérifiez chaque étage de 1 à j
dp[i][0] = 0, i = 1…K # pas de plancher, pas de chute nécessaire pour obtenir le plancher optimal
dp[i][1] = 1, i = 1…K # un étage, vérifier une seule fois

Pour obtenir une relation récursive, considérons un cas de test : 3 œufs et 100 étages.

Pour le prochaine lâché, je peux choisir un étage de 1 à 100, disons que je choisis 25.

Il y a 2 résultats possibles pour ce lâché :

l’œuf s’est cassé, j’ai maintenant 2 œufs, et le plancher à choisir devient 1~24.
l’oeuf reste en sécurité, j’ai encore 3 oeufs, et le plancher à choisir devient 26~100.

Pensez au scénario du pire cas et utilisez la définition dp ci-dessus, nous pouvons décrire la situation d’obtention du plancher optimal en choisissant le plancher 25 pour la prochaine lâché comme :

dp[3][100] = 1 + max(dp[2][24], dp[3][75])

Outre l’étage 25, en terme de prochain lâché , nous pouvons également choisir l’étage de 1 à 100.

Chaque lâché serait similaire au cas du 25 ci-dessus. Le résultat final serait le minimum de tous les choix possibles d’étages suivants à déposer :

dp[3][100] = min(…, 1 + max(dp[2][23], dp[3][76]), 1 + max(dp[2][24], dp[3][75]), 1 + max(dp[2][25], dp[3][74]), …) (prenons l’étage 24, 25, 26 comme exemple)

Pour généraliser l’exemple ci-dessus, la formule dp serait :

dp[i][j] = min(1 + max(dp[i-1][k-1], dp[i][j-k])), k = 1,2,…j

Par conséquent, nous définissons dp[i][j] comme le plus petit nombre de gouttes pour obtenir le plancher optimal avec i œufs et j planchers restants.

Voici une première solution en force brute en O(kn^2)

egg drop force brute

Cependant, cette idée est très brute force, car vous vérifiez toutes les possibilités.

Je considère donc ce problème d’une manière différente:
dp[M][K]signifie que, étant donné K oeufs et M coups, quel est le nombre maximum d’étages que nous pouvons vérifier.

L’équation dp est : dp[m][k] = dp[m – 1][k – 1] + dp[m – 1][k] + 1,
ce qui signifie que nous prenons 1 mouvement vers un étage, si l’œuf se casse, alors nous pouvons vérifier dp[m – 1][k – 1] étages. si l’œuf ne se casse pas, alors nous pouvons vérifier dp[m – 1][k] étages.

Ce qui donnerai le code suivant :

egg drop programmation dynamique

Ne tenter pas ce code, vous aurez un TLE ! Il faudrait l’optimiser avec un Binary Tree que l’on fera dans un autre cours !

Exercice 15

Les démons ont capturé la princesse et l’ont emprisonnée dans le coin inférieur droit d’un donjon. Le donjon se compose de m x n pièces disposées dans une grille 2D. Notre vaillant chevalier est initialement positionné dans la salle en haut à gauche et doit se frayer un chemin à travers le donjon pour sauver la princesse.

Le chevalier a un nombre de points de vie initial représenté par un entier positif. Si à tout moment ses points de vie tombe à 0 ou en dessous, il meurt immédiatement.

Certaines pièces sont gardées par des démons (représentés par des nombres entiers négatifs), de sorte que le chevalier perd de la santé en entrant dans ces pièces ; les autres salles sont soit vides (représentées par 0), soit contiennent des orbes magiques qui augmentent la santé du chevalier (représentées par des nombres entiers positifs).

Pour atteindre la princesse le plus rapidement possible, le chevalier décide de se déplacer uniquement vers la droite ou vers le bas à chaque pas.

Donner la santé initiale minimale du chevalier afin qu’il puisse sauver la princesse.

Notez que n’importe quelle pièce peut contenir des menaces ou des power-ups, même la première pièce dans laquelle le chevalier entre et la pièce en bas à droite où la princesse est emprisonnée.

donjon programmation dynamique

Entrée : donjon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Sortie : 7
Explication : La santé initiale du chevalier doit être d’au moins 7 s’il suit le chemin optimal : DROITE-> DROITE -> BAS -> BAS.

Probablement lorsque vous voyez ce problème et que vous avez une certaine expérience dans ce type de problèmes, vous pouvez deviner qu’il s’agit d’un problème de programmation dynamique. Cependant, même si vous comprenez cela, il n’est pas facile de le résoudre. Utilisons dp de haut en bas, c’est-à-dire Soit dp[i][j] le hp minimum dont nous avons besoin pour atteindre la princesse si nous partons du point (i,j). Considérons l’exemple suivant :

donjon programmation dynamique

Ajoutons une ligne factice en bas et une colonne factice à droite pour gérer plus facilement les cas de bordure. Nous le remplissons d’infinis, sauf deux – voisins de notre princesse. Je l’expliquerai un peu plus tard.

Comment évaluer dp[i][j] ? Nous devons examiner deux cellules : dp[i+1][j] et dp[i][j+1] et évaluer deux candidats possibles : dp[i+1][j]-donjon[i][j] et dp[i][j+1]-donjon[i][j].

  1. Si au moins un de ces deux nombres est négatif, cela signifie que l’on peut survivre avec juste 1 hp : (regardez le nombre +30 dans notre tableau par exemple)
  2. Si ces deux nombres sont positifs, il faut en prendre le minimum, voir par exemple le nombre -10 dans notre tableau : pour survivre il faut soit 5- -10 = 15 si on va à droite et 1- -10 = 11 si on descend, bien sûr on choisit 11.

Ces conditions peuvent être écrites sur une équation : dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-donjon[i][j],1).

Enfin, pourquoi j’ai mis 1 à 2 voisins de princesse ? Pour rendre cette formule valable pour la cellule princesse : si nous avons un nombre négatif comme -5 dans cette cellule, nous avons besoin de 6 gp pour survivre, si nous avons un nombre non négatif dans cette cellule, nous avons besoin de 1 gp pour survivre.

donjon programmation dynamique

La complexité en temps et espace est de O(nm)

donjon programmation dynamique

Il est également possible de le faire avec dp descendant, mais dans ce cas, vous devez utiliser la recherche binaire, car vous ne savez pas à l’avance si vous survivez à partir de x HP ou non. La complexité sera O(nm log(MAX_HP)) dans ce cas.

Exercice 16

On vous donne une grille matricielle lignes x cols représentant un champ de cerises où grid[i][j] représente le nombre de cerises que vous pouvez collecter à partir de la cellule (i, j).

Vous avez deux robots qui peuvent ramasser des cerises pour vous :

Le robot #1 est situé dans le coin supérieur gauche (0, 0) et
Le robot #2 est situé dans le coin supérieur droit (0, cols – 1).

Renvoyez le nombre maximum de collecte de cerises à l’aide des deux robots en suivant les règles ci-dessous :

À partir d’une cellule (i, j), les robots peuvent se déplacer vers la cellule (i + 1, j – 1), (i + 1, j) ou (i + 1, j + 1).
Lorsqu’un robot traverse une cellule, il ramasse toutes les cerises et la cellule devient une cellule vide.
Lorsque les deux robots restent dans la même cellule, un seul prend les cerises.
Les deux robots ne peuvent à aucun moment sortir de la grille.
Les deux robots doivent atteindre la rangée inférieure de la grille.

pickup programmation dynamique

Entrée : grille = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Sortie : 28

Explication : Les trajectoires des robots 1 et 2 sont respectivement décrites en vert et en bleu.
Cerises prises par Robot #1, (1 + 9 + 5 + 2) = 17.
Cerises prises par Robot #2, (1 + 3 + 4 + 3) = 11.
Total de cerises : 17 + 11 = 28.

Dans ce problème, nous supposerons que les deux robots passeront à la rangée suivante en même temps afin qu’ils restent tous les deux dans la même rangée. Ce sera le premier aperçu pour résoudre ce problème.

Comme décrit dans l’énoncé du problème, nous pouvons nous déplacer dans 3 directions (i+1, j-1) , (i+1, j) ou (i+1, j+1). Tous dans la ligne suivante mais avec une colonne différente.

Puisque nous avons 3 directions pour chaque robot, il y a donc à chaque rangée 9 (3 x 3) états vers lesquels nous pouvons nous déplacer. (3 états pour le premier robot et 3 états pour le deuxième robot donc c’est 3 x 3).

Et comme l’indique l’indice, nous devons avoir un tableau DP de 4 lignes. Comme il s’agit d’un tableau à 3 dimensions, il y aura un tableau à 2 dimensions qui sera n * n, c’est-à-dire no. de colonne * no. de colonne. Où la ligne sera définie par la position de la colonne Robot1 et la colonne précisera la position de la colonne Robot2.

pickup programmation dynamique

Au départ, nous savons que robot1 est à la position 0 et que robot2 est à la position colonne – 1, c’est-à-dire la dernière colonne.

Nous devons remplir dp[0] c’est-à-dire la 1ère ligne et dans cette 1ère ligne, la position de colonne pour le robot sera (0, 2) car 0 signifie la position de colonne pour robot1 et 2 signifie la position de colonne pour robot2 dans la grille.

programmation dynamique pickup

Lorsque nous remplissons l’espace, nous obtenons la valeur 3 + 1 soit 4

Maintenant, nous devons remplir la 2ème rangée. Et dans la 2ème ligne également, il y aura une matrice n * m. Si nous prenons la position précédente de robot1 comme étant 0, nous avons 3 colonnes dans lesquelles il peut aller dans la ligne suivante, c’est-à-dire col {-1, 0, 1}. Comme col1 est hors limite, nous rejetons ce « -1 » et ne gardons que « 0, 1 »

Et pareil le robot2 est en 2, on peut soit atteindre la col {1, 2, 3}. Comme col3 est hors limite, nous le rejetons « 3 » et ne gardons que « 1, 2 »

Maintenant, lorsque nous créons la combinaison de toutes les colonnes que robot1 et robot2 peuvent être, nous obtenons 4 valeurs et lorsque nous la remplissons, ce sera :

pickup programmation dynamique

Donc, si nous regardons pour (0, 1) la valeur qui revient sera grid[0][1] + grid[1][1] + prev. Mais pour (1,1) ce sera grid[1][1] + prev.

Si on parle maintenant de code. Prenons dp[row][column][column] notre programmation dynamique. Au début col1=0 et col2=column-1 (emplacement des robots).

Nous avons la solution max=dp[0][col1][col2].

Voici le code permettant de remplir pour chaque valeur croissante de dp[raw][][]

// now comes a part where we need to iterate over each row;
        for(int i = 1; i < row; i++){ // each row starting with 1
            // In this each row of dp, we need to excise our logic picking that particular column, as the starting position
            // we need to loop on all the columns precise in this row
            // as i told there will be n * m column
            for(int c1 = 0; c1 < col; c1++){ 
                for(int c2 = 0; c2 < col; c2++){
                    // now from every column we need to fill the cube; for all the combinations or all the cell we can reach; with respective robot1 & robot2
                    // now we need to 1st take the previous value, that we disucssed
                    int prev = dp[i - 1][c1][c2]; 
                    if(prev >= 0){ // if that the case, we need to perform our operation, if it is a -ve value it means that we haven't reach yet that particular cell. And above that's why we intialize the whole array with -1
                        // Now we need to iterate over all the combinations of column that c1 & c2 can be in. For that we had define a direction array at the top
                        for(int d1: dir){ // for c1 we have the direction "d1" and we iterate over it
                            col1 = d1 + c1; // and column1 will be d1 + c1
                            for(int d2: dir){ // for c2 we have the direction "d2" and we iterate over it
                                col2 = d2 + c2; // and column2 will be d2 + c2
                            // Now we need to check is the new col1 & col2 are in the range of 0 & col. And for that we need to create a new method, which will check is the new col1 & col2 are in the range
                                if(inRange(col1, col) && inRange(col2, col)){
                                    dp[i][col1][col2] = Math.max(dp[i][col1][col2], prev+(col1 == col2 ? grid[i][col1] : (grid[i][col1] + grid[i][col2]))); // if the value are int this range, we need to update the col1 & col2 position in the i'th row
                                    max = Math.max(max, dp[i][col1][col2]); // we need to update the maximum at each step. Taking max of max value & also the new column that we have filled
                                }
                            }
                        }
                    }
                    
                }
            }
        }
        return max; //eturn max at the end

Appelons dp’ l’approche montante. Voici un code mieux optimisé en utilisant une approche descendante du problème d’origine.

dp[k][i][j] indique si les deux robots partent de grid[k][i] et grid[k][j] le nombre total maximum de cerises qu’ils peuvent enfin ramasser. Notez qu’ils ne peuvent se déplacer qu’en bas.

Après avoir rempli dp, la réponse finale est dp[0][0][COL_NUM – 1]

Pour la dernière ligne de grille, on a dp[-1][i][j] = grille[-1][i] si i == j sinon grille[-1][i] + grille[-1][j]. Notez que si 2 robots restent au même endroit, ils ne peuvent ramasser qu’une seule fois.

Pour les autres rangées, nous devons parcourir toutes les combinaisons de directions 3 * 3 qu’ils peuvent choisir dans la couche suivante et trouver le maximum, car pour chaque robot, il y a 3 directions dans lesquelles ils peuvent se déplacer. 

pickup programmation dynamique

On aura donc le code suivant :

pickup programmation dynamique

Ce n’est pas très optimal. Voici un code mieux optimisé en python (en 2D avec une approche DFS) :

pickup programmation dynamique

Partager