Tutoriel pour la programmation dynamique | CodeChef (2023)

Introduction à la programmation dynamique

Programmation dynamique (généralement appeléeDP) est une technique très puissante pour résoudre une classe particulière de problèmes. Cela demande une formulation très élégante de l'approche et une pensée simple et la partie codage est très facile. L'idée est très simple, si vous avez résolu un problème avec l'entrée donnée, enregistrez le résultat pour référence future, afin d'éviter de résoudre à nouveau le même problème."Souviens-toi de ton passé":) . Si le problème donné peut être divisé en sous-problèmes plus petits et que ces sous-problèmes plus petits sont à leur tour divisés en sous-problèmes encore plus petits, et dans ce processus, si vous observez des sous-problèmes qui se chevauchent, alors c'est un gros indice pourDP. De plus, les solutions optimales aux sous-problèmes contribuent à la solution optimale du problème donné (appelé lePropriété optimale de la sous-structure).

Il y a deux façons de le faire.

De haut en bas

Commencez à résoudre le problème donné en le décomposant. Si vous voyez que le problème a déjà été résolu, renvoyez simplement la réponse enregistrée. S'il n'a pas été résolu, résolvez-le et enregistrez la réponse. C'est généralement facile à penser et très intuitif. Ceci est appeléMémoïsation.

De bas en haut

Analysez le problème et voyez l'ordre dans lequel les sous-problèmes sont résolus et commencez à résoudre à partir du sous-problème trivial, jusqu'au problème donné. Dans ce processus, il est garanti que les sous-problèmes sont résolus avant de résoudre le problème. Ceci est appeléProgrammation dynamique.

Notez que diviser pour régner est une technique légèrement différente. En cela, nous divisons le problème en sous-problèmes qui ne se chevauchent pas et les résolvons indépendamment, comme danstri par fusionettri rapide.

Au cas où vous souhaiteriez voir des [[https://www.thelearningpoint.net/computer-science/dynamic-programming|visualisations liées à la programmation dynamique, essayez ceci]].

En complément de la programmation dynamique, il y a les [[https://www.thelearningpoint.net/computer-science/greedy-algorithms|Greedy Algorithms]] qui prennent une décision une fois pour toutes à chaque fois qu'ils doivent faire un choix, de manière à ce que cela conduise à une solution quasi optimale. Une solution de Programmation Dynamique est basée sur le principe deInduction mathematiqueles algorithmes gourmands nécessitent d'autres types de preuves.

Guerre froide entre récursivité systématique et programmation dynamique

Récursivitéutilise l'approche descendante pour résoudre le problème, c'est-à-dire qu'il commence par le problème principal (principal), puis le divise en sous-problèmes et résout ces sous-problèmes de la même manière. Dans cette approche, le même sous-problème peut se produire plusieurs fois et consommer plus de cycle CPU, augmentant ainsi la complexité temporelle. Alors que dans la programmation dynamique, le même sous-problème ne sera pas résolu plusieurs fois, mais le résultat précédent sera utilisé pour optimiser la solution. par exemple. Danssérie de Fibonacci:-

Fib(4) = Fib(3) + Fib(2)

= (Fib(2) + Fib(1)) +Fib(2)

l"> =((Fib(1) + Fib(0)) +Fib(1)) +Fib(2)

=((Fib(1) + Fib(0)) +Fib(1)) + (Fib(1)+Fib(0))

Ici, l'appel à Fib(1) et Fib(0) est effectué plusieurs fois. cas de Fib(100) ces appels seraient comptés pour millions de fois. Par conséquent, il y a beaucoup de gaspillage de ressources (cycles CPU et mémoire pour stocker des informations sur la pile).

Dansprogrammation dynamiquetous les sous-problèmes sont résolus même ceux qui ne sont pas nécessaires, mais dansrécursivitéseuls les sous-problèmes requis sont résolus. La solution par programmation dynamique doit donc être correctement encadrée pour supprimer cet effet néfaste.

Par ex. En combinatoire, C(n.m) = C(n-1,m) + C(n-1,m-1).

1 1 1 1 2 1 1 3 3 1 1 4 6 4 11 5 10 10 5 1

En solution simple, il faudrait construire tout le triangle pascal pour calculer C(5,4) mais la récursivité pourrait faire gagner beaucoup de temps.

La programmation dynamique et la récursivité fonctionnent de manière presque similaire dans le cas de sous-problèmes non superposés. Dans un tel problème, d'autres approches pourraient être utilisé comme "diviser pour régner".

Même certains des codeurs les mieux notés se trompent souvent dans des problèmes de DP délicats. Les gourous du DP suggèrent que le DP est un art et qu'il s'agit de la pratique. Plus vous résolvez de problèmes DP, plus il devient facile de relier un nouveau problème à celui que vous avez déjà résolu et d'ajuster votre réflexion très rapidement. Cela ressemble à de la magie quand vous voyez quelqu'un résoudre si facilement un DP délicat. Il est temps pour vous d'apprendre un peu de magie maintenant :). Commençons par un problème très simple.

Étapes minimales à un

Énoncé du problème :

Sur un entier positif, vous pouvez effectuer l'une des 3 étapes suivantes.1.)Soustrayez-y 1. ( n = n - 1 ) ,2.)Si c'est divisible par 2, divisez par 2. ( si n % 2 == 0 , alors n = n / 2 ) ,3.)Si c'est divisible par 3, divisez par 3. ( si n % 3 == 0 , alors n = n / 3 ). Maintenant la question est, étant donné un entier positifn, trouver le nombre minimum d'étapes qui prendnà 1

ex : 1.)Pour n = 1 , sortie : 0 2.) Pour n = 4 , sortie : 2 ( 4/2= 2/2= 1 ) 3.) Pour n = 7 , sortie : 3 ( 7-1= 6/3= 2/2= 1 )

Approche / Idée :

On peut penser à choisir goulûment le pas, ce qui faitnaussi bas que possible et continuez ainsi jusqu'à ce qu'il atteigne 1. Si vous observez attentivement, la stratégie gourmande ne fonctionne pas ici. Ex : Donnén= 10 , Gourmand --> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 étapes ). Mais la manière optimale est --> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 étapes ). Donc, nous devons essayer toutes les étapes possibles que nous pouvons faire pour chaque valeur possible dennous rencontrons et choisissons le minimum de ces possibilités.

Tout commence par la récursivité :). F(n) = 1 + min{ F(n-1) , F(n/2) , F(n/3) } si (n>1) , sinon 0 (c'est-à-dire F(1) = 0 ) . Maintenant que nous avons notre équation de récurrence, nous pouvons commencer à coder la récursivité. Attendez .., y a-t-il des sous-problèmes qui se chevauchent? OUI. La solution optimale à une entrée donnée dépend-elle de la solution optimale de ses sous-problèmes ? Oui... Bingo ! son DP :) Donc, nous stockons simplement les solutions aux sous-problèmes que nous résolvons et les utilisons plus tard, comme dans la mémorisation .. ou nous partons du bas et remontons jusqu'au donnén, comme dans dp. Comme c'est le tout premier problème que nous examinons ici, voyons les deux codes.

Mémoïsation

int mémo[n+1] ; // nous allons initialiser les éléments à -1 ( -1 signifie, pas encore résolu )int getMinSteps ( int n ){ if ( n == 1 ) return 0; // cas de base if( memo[n] != -1 ) return memo[n]; // nous l'avons déjà résolu :) int r = 1 + getMinSteps( n - 1 ); // Pas '-1' . 'r' contiendra finalement la réponse optimale if( n%2 == 0 ) r = min( r , 1 + getMinSteps( n / 2 ) ) ; // '/2' step if( n%3 == 0 ) r = min( r , 1 + getMinSteps( n / 3 ) ) ; // '/3' étape mémo[n] = r ; // enregistre le résultat. Si vous oubliez cette étape, alors c'est la même chose que la récursivité simple. retourner r ;}

DP ascendant

int getMinSteps (int n){ int dp[n+1], je ; dp[1] = 0 ; // cas trivial pour( je = 2 ; je < = n ; je ++ ) { dp[i] = 1 + dp[i-1] ; si(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] ); si(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] ); } renvoie dp[n] ;}

Les deux approches sont bonnes. Mais il faut aussi faire attention à la surcharge impliquée dans les appels de fonction dans Memoization, ce qui peut donner rarement une erreur StackOverFlow ou TLE.

Problème : Sous-suite croissante la plus longue

Le problème de la plus longue sous-séquence croissante consiste à trouver la plus longue sous-séquence croissante d'une séquence donnée. Soit une suite S= {un₁ , un₂ , un₃, un₄,............., un_n-1, un_n } nous devons trouver un sous-ensemble le plus long tel que pour tout j et i, jjje.

Tout d'abord, nous devons trouver la valeur des sous-suites les plus longues (LS_je) à chaque index i avec le dernier élément de la séquence étant un_je. Puis le plus grand LS_jeserait la plus longue sous-séquence dans la séquence donnée. Pour commencer LS_jeest attribué à un puisqu'un_jeest un élément de la séquence (dernier élément). Alors pour tout j tel que jjje, nous trouvons le plus grand LS_jet l'ajouter à LS_je. Alors l'algorithme prend O(n²) temps.

Pseudo-code pour trouver la longueur de la plus longue sous-séquence croissante :

La complexité de ces algorithmes pourrait être réduite en utilisant une meilleure structure de données plutôt qu'un tableau. Stockagetableau prédécesseur et variable comme la plus grande_séquences_so_far et son index permettrait de gagner beaucoup de temps.

Un concept similaire pourrait être appliqué pour trouver le chemin le plus long dans un graphe acyclique dirigé.

---------------------------------------------------------------------------

pour i=0 à n-1

LS[i]=1

pour j=0 à i-1

si (a[i] > a[j] et LS[i]<=LS[j])

LS[i] = LS[j]+1

pour i=0 à n-1

si (le plus grand < LS[i])

le plus grand = LS[i]

Problème : Sous-séquence commune la plus longue (LCS)

Sous-séquence commune la plus longue - Programmation dynamique - Tutoriel et code source du programme C

Étant donné une séquence d'éléments, une sous-séquence de celle-ci peut être obtenue en supprimant zéro ou plusieurs éléments de la séquence, en préservant l'ordre relatif des éléments. Notez que pour une sous-chaîne, les éléments doivent être contigus dans une chaîne donnée, pour une sous-séquence, ce n'est pas nécessaire. Par exemple : S1="ABCDEFG" est la chaîne donnée. "ACEG", "CDF" sont des sous-séquences, alors que "AEC" ne l'est pas. Pour une ficelle de longueurnle nombre total de sous-séquences est 2ⁿ(Chaque personnage peut être pris ou non pris). Maintenant, la question est de savoir quelle est la longueur de la plus longue sous-séquence commune aux deux chaînes S1 et S2 données. Notons la longueur de S1 par N et la longueur de S2 par M.

Force brute

Considérez chacun des 2^Nsous-séquences de S1 et vérifiez si c'est aussi une sous-séquence de S2, et prenez la plus longue de toutes ces sous-séquences. Clairement très chronophage.

Récursivité

Pouvons-nous décomposer le problème de trouver le SCL de S1[1...N] et S2[1...M] en sous-problèmes plus petits ?

Mémoire limitée DP

[faire , fibonacci , LCS etc., ]

Problèmes de pratique

1. Autres problèmes de DP classiques :0-1 Problème KnapSack (tutoriel et programme C),Matrix Chain Multiplication (tutoriel et programme C), somme de sous-ensemble, changement de pièces,All to all Shortest Paths in a Graph (tutoriel et programme C),Assemblage à la chaîne ou tri topographique

Vous pouvez vous référer à certains d'entre eux dans leSite algorithmique

2. Le tirage au sort (concours du 09 juin).https://www.codechef.com/problems/D2/

3. Trouvez le nombre de sous-séquences croissantes dans la sous-séquence donnée de longueur 1 ou plus.

4. COMBINAISON-

Pour voir les problèmes sur la visite DPce lien

5.TopCoder -Zigzag

6.TopCoder -Éviter les routes- Un problème simple et agréable à pratiquer

7. Pour plus de problèmes DP et différentes variétés, reportez-vous à une très belle collectionhttps://www.codeforces.com/blog/entry/325

8..Archives des problèmes de TopCoder

Ceci n'est pas lié à la programmation dynamique, mais comme 'trouver le n^e[[https://www.thelearningpoint.net/computer-science/learning-python-programming-and-data-structures/learning-python-programming-and-data-structures--tutorial-7--functions-and-recursion-multiple-function-arguments-and-partial-functions|nombre de Fibonacci]' est discuté, il serait utile de connaître une technique très rapide pour résoudre le même problème.

Trouver n^eNombre de Finobacci en O(log n)

Remarque : La méthode décrite ici pour trouver le n^eLe nombre de Fibonacci utilisant la programmation dynamique s'exécute en temps O (n). Il existe encore une meilleure méthode pour trouver F(n), lorsque n devient aussi grand que 10¹⁸(comme F(n) peut être très grand, tout ce que nous voulons, c'est trouver le F(N)%MOD , pour un MOD donné).

Considérons la récurrence de Fibonacci F(n+1) = F(n) + F(n-1). Nous pouvons représenter cela sous la forme d'une matrice, nous avons montré ci-dessous.

Regardez la matrice A = [ [ 1 1 ] [ 1 0 ] ] . Multiplier A par [ F(n) F(n-1) ] nous donne [ F(n+1) F(n) ] , donc... nous

commencer par [ F(1) F(0) ] , en le multipliant par Aⁿnous donne [ F(n+1) F(n) ] , il ne reste donc plus qu'à trouver le n^epuissance de la matrice A. Eh bien, cela peut être calculé en temps O(log n), par doublage récursif. L'idée est de trouver Aⁿ, on peut faire R = A^n/2xA^n/2et si n est impair, nous devons multiplier par un A à la fin. Le pseudo-code suivant montre la même chose.

[code]

Matrice findNthPower( Matrice M , puissance n )

{

si( n == 1 ) renvoie M ;

Matrice R = findNthPower ( M , n/2 );

R = RxR ; // multiplication matricielle

si( n%2 == 1 ) R = RxM ; // multiplication matricielle

retourner R ;

}

[/code]

Vous pouvez en savoir plus à ce sujetici

Cette méthode est en général applicable à la résolution de toute équation de récurrence linéaire homogène, par exemple : G(n) = a.G(n-1) + b.G(n-2) - c.G(n-3) , tout ce que nous avons à faire est de la résoudre et de trouver la matrice A et d'appliquer la même technique.

Tutoriels et codes sources du programme C pour les problèmes courants de programmation dynamique

Les techniques de programmation dynamique sont principalement basées sur le principe de l'induction mathématique contrairement aux algorithmes gloutons qui tentent de faire une optimisation basée sur des décisions locales, sans regarder les informations ou les tables précédemment calculées. Certains cas classiques d'algorithmes gourmands sont le [[https://www.thelearningpoint.net/computer-science/algorithms-greedy-algorithms---fractional-knapsack-problems-task-scheduling-problem|greedy knapsack problem]], [[https://www.thelearningpoint.net/computer-science/algorithms-greedy-algorithms---data-com pression-using-huffman-encoding|arbres de compression huffman]], [[https://www.thelearningpoint.net/computer-science/algorithms-greedy-algorithms---fractional-knapsack-problems-task-scheduling-problem|ordonnancement des tâches]]. [[https://www.thelearningpoint.net/computer-science/arrays-and-sorting-insertion-sort--with-c-program-source-code|Insertion sort]] est un exemple de programmation dynamique, [[https://www.thelearningpoint.net/computer-science/arrays-and-sorting-selection-sort--with-c-program-source-code|selection sort]] est un exemple d'algorithmes gourmands,[[https://www.thelearningpoint .net/computer-science/arrays-and-sorting-merge-sort--with-c-program-source-code|Merge Sort]] et [[https://www.thelearningpoint.net/computer-science/arrays-and-sorting-quick-sort--with-c-program-source-code|Quick Sort]] sont des exemples de diviser pour régner. Ainsi, différentes catégories d'algorithmes peuvent être utilisées pour atteindre le même objectif - dans ce cas, le tri.