logo

TechCodeview

Dynamisch Programmeren of DP

Dynamisch programmeren is een methode die in de wiskunde en informatica wordt gebruikt om complexe problemen op te lossen door ze op te splitsen in eenvoudiger deelproblemen. Door elk deelprobleem slechts één keer op te lossen en de resultaten op te slaan, worden overbodige berekeningen vermeden, wat leidt tot efficiëntere oplossingen voor een breed scala aan problemen. Dit artikel biedt een gedetailleerde verkenning van dynamische programmeerconcepten, geïllustreerd met voorbeelden.

converteer boolean naar string

Dynamisch programmeren

Inhoudsopgave



Wat is dynamisch programmeren (DP)?

Dynamische programmering (DP) is een methode die in de wiskunde en informatica wordt gebruikt om complexe problemen op te lossen door ze op te splitsen in eenvoudiger deelproblemen. Door elk deelprobleem slechts één keer op te lossen en de resultaten op te slaan, worden overbodige berekeningen vermeden, wat leidt tot efficiëntere oplossingen voor een breed scala aan problemen.

Hoe werkt dynamisch programmeren (DP)?

  • Identificeer subproblemen: Verdeel het hoofdprobleem in kleinere, onafhankelijke deelproblemen.
  • Winkeloplossingen: Los elk deelprobleem op en sla de oplossing op in een tabel of array.
  • Opbouwoplossingen: Gebruik de opgeslagen oplossingen om de oplossing voor het hoofdprobleem op te bouwen.
  • Vermijd redundantie: Door oplossingen op te slaan, zorgt DP ervoor dat elk deelprobleem slechts één keer wordt opgelost, waardoor de rekentijd wordt verkort.

Voorbeelden van dynamisch programmeren (DP)

Voorbeeld 1: Beschouw het probleem van het vinden van de Fibonacci-reeks:

Fibonacci-reeks: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Brute Force-aanpak:

Om het n-de Fibonacci-getal te vinden met behulp van een brute force-aanpak, voegt u eenvoudigweg de (n-1)de En (n-2)de Fibonacci-getallen. Dit zou werken, maar het zou inefficiënt zijn voor grote waarden van N , omdat hiervoor alle voorgaande Fibonacci-getallen moeten worden berekend.

Dynamische programmeerbenadering:

Fibonacci-serie met behulp van dynamisch programmeren

  • Deelproblemen: F(0), F(1), F(2), F(3), …
  • Winkeloplossingen: Maak een tabel om de waarden van F(n) op te slaan terwijl ze worden berekend.
  • Opbouwoplossingen: Zoek voor F(n) F(n-1) en F(n-2) op in de tabel en tel deze op.
  • Vermijd redundantie: De tabel zorgt ervoor dat elk deelprobleem (bijvoorbeeld F(2)) slechts één keer wordt opgelost.

Door DP te gebruiken, kunnen we de Fibonacci-reeks efficiënt berekenen zonder dat we subproblemen opnieuw hoeven te berekenen.

prioriteit wachtrij java

Voorbeeld 2: Langste gemeenschappelijke deelreeks (de langste deelreeks vinden die gemeenschappelijk is voor twee tekenreeksen)

Voorbeeld 3: Kortste pad in een grafiek (het kortste pad vinden tussen twee knooppunten in een grafiek)

Voorbeeld 4: Knapzakprobleem (het vinden van de maximale waarde van items die in een knapzak met een bepaalde capaciteit kunnen worden geplaatst)

Wanneer gebruik je dynamisch programmeren (DP)?

Dynamisch programmeren is een optimalisatietechniek die wordt gebruikt bij het oplossen van problemen en die uit de volgende kenmerken bestaat:

1. Optimale onderbouw:

Optimale onderbouw betekent dat we de optimale resultaten van deelproblemen combineren om het optimale resultaat van het grotere probleem te bereiken.

wat zijn de afmetingen van mijn computerscherm

Voorbeeld:

Denk eens aan het probleem van het vinden van de minimale kosten pad in een gewogen grafiek van a bron knooppunt naar een bestemming knooppunt. We kunnen dit probleem opsplitsen in kleinere deelproblemen:

  • Vind de minimum kosten pad van de bron knooppunt naar elk tussenliggend knooppunt.
  • Vind de minimum kosten pad van elk tussenliggend knooppunt naar de bestemming knooppunt.

De oplossing voor het grotere probleem (het vinden van het minimale kostenpad van het bronknooppunt naar het bestemmingsknooppunt) kan worden opgebouwd uit de oplossingen voor deze kleinere deelproblemen.

2. Overlappende deelproblemen:

Dezelfde deelproblemen worden herhaaldelijk opgelost in verschillende delen van het probleem.

Voorbeeld:

Denk eens aan het probleem van het berekenen van de Fibonacci-reeks . Om het Fibonacci-getal bij index te berekenen N , moeten we de Fibonacci-getallen bij indices berekenen n-1 En n-2 . Dit betekent dat het subprobleem van het berekenen van het Fibonacci-getal bij index n-1 wordt twee keer gebruikt bij de oplossing van het grotere probleem van het berekenen van het Fibonacci-getal bij de index N .

Benaderingen van dynamisch programmeren (DP)

Dynamisch programmeren kan op twee manieren worden bereikt:

1. Top-down benadering (memoriseren):

In de top-down benadering, ook wel bekend als memoriseren , beginnen we met de uiteindelijke oplossing en splitsen deze recursief op in kleinere deelproblemen. Om overbodige berekeningen te voorkomen, slaan we de resultaten van opgeloste deelproblemen op in een memoisatietabel.

Laten we de top-downbenadering samenvatten:

  • Begint met de uiteindelijke oplossing en splitst deze recursief op in kleinere deelproblemen.
  • Slaat de oplossingen voor deelproblemen op in een tabel om overbodige berekeningen te voorkomen.
  • Geschikt als het aantal deelproblemen groot is en veel ervan opnieuw worden gebruikt.

2. Bottom-up-benadering (tabellering):

In de bottom-up benadering, ook wel bekend als tabel , beginnen we met de kleinste deelproblemen en bouwen we geleidelijk op naar de uiteindelijke oplossing. De resultaten van opgeloste deelproblemen slaan we op in een tabel om overbodige berekeningen te voorkomen.

Laten we de bottom-up benadering uiteenzetten:

aaneenschakeling van Java-tekenreeks
  • Begint met de kleinste deelproblemen en bouwt geleidelijk op naar de uiteindelijke oplossing.
  • Vult een tabel met oplossingen voor deelproblemen op een bottom-up manier.
  • Geschikt wanneer het aantal deelproblemen klein is en de optimale oplossing direct kan worden berekend op basis van de oplossingen voor kleinere deelproblemen.

Dynamisch programmeren (DP) Algoritme

Dynamisch programmeren is een algoritmische techniek die complexe problemen oplost door ze op te splitsen in kleinere deelproblemen en de oplossingen ervan op te slaan voor toekomstig gebruik. Het is vooral effectief bij problemen die bevatten overlappende deelproblemen En optimale onderbouw.

Algemene algoritmen die dynamische programmering gebruiken:

  • Langste gemeenschappelijke vervolgreeks (LCS): Vindt de langste gemeenschappelijke deelreeks tussen twee tekenreeksen.
  • Kortste pad in een grafiek: Vindt het kortste pad tussen twee knooppunten in een grafiek.
  • Knapzakprobleem: Bepaalt de maximale waarde van items die in een knapzak met een bepaalde capaciteit kunnen worden geplaatst.
  • Vermenigvuldiging van matrixketens: Optimaliseert de volgorde van matrixvermenigvuldiging om het aantal bewerkingen te minimaliseren.
  • Fibonacci-reeks: Berekent het nde Fibonacci-getal.

Voordelen van dynamisch programmeren (DP)

Dynamisch programmeren heeft een breed scala aan voordelen, waaronder:

  • Voorkomt dat dezelfde subproblemen meerdere keren opnieuw moeten worden berekend, wat tot aanzienlijke tijdbesparingen leidt.
  • Zorgt ervoor dat de optimale oplossing wordt gevonden door alle mogelijke combinaties af te wegen.
  • Breekt complexe problemen op in kleinere, beter beheersbare deelproblemen.

Toepassingen van dynamisch programmeren (DP)

Dynamisch programmeren heeft een breed scala aan toepassingen, waaronder:

  • Optimalisatie: Knapzakprobleem, kortste padprobleem, maximum subarrayprobleem
  • Computertechnologie: Langste gemeenschappelijke deelreeks, bewerkingsafstand, stringmatching
  • Operationeel onderzoek: Voorraadbeheer, planning, toewijzing van middelen

Laten we nu een uitgebreide routekaart verkennen om dynamisch programmeren onder de knie te krijgen.

Leer de basis van dynamisch programmeren (DP)

Geavanceerde concepten in dynamisch programmeren (DP)

  • Bitmasking en dynamische programmering | Set 1
  • Bitmasking en dynamische programmering | Set-2 (TSP)
  • Cijfer DP | Invoering
  • Som over subsets | Dynamisch programmeren

Dynamische programmering (DP) Problemen

We hebben standaard dynamische programmeerproblemen (DP) in drie categorieën ingedeeld: eenvoudig, gemiddeld en moeilijk.

1. Eenvoudige problemen met dynamisch programmeren (DP)

  • Fibonacci-getallen
  • nde Catalaans nummer
  • Belnummers (aantal manieren om een ​​set te verdelen)
  • Binominale coëfficiënt
  • Probleem met het wisselen van munten
  • Subsetsomprobleem
  • Bereken nCr % p
  • Een staaf snijden
  • Algoritme voor hekwerk schilderen
  • Langste gemeenschappelijke vervolgreeks
  • Langste stijgende vervolgreeks
  • Langste deelreeks zodat het verschil tussen aangrenzende delen één is
  • Maximale vierkante submatrix met alle 1-en
  • Min. kostenpad
  • Minimum aantal sprongen om het einde te bereiken
  • Langste gemeenschappelijke substring (ruimte-geoptimaliseerde DP-oplossing)
  • Tel manieren om de zoveelste trap te bereiken met behulp van stap 1, 2 of 3
  • Tel alle mogelijke paden van linksboven naar rechtsonder van een mXn-matrix
  • Unieke paden in een raster met obstakels

2. Middelgrote problemen bij dynamisch programmeren (DP)

  • Floyd Warshall-algoritme
  • Bellman-Ford-algoritme
  • 0-1 Knapzakprobleem
  • Artikelen bedrukken in 0/1 knapzak
  • Ongebonden knapzak (herhaling van items toegestaan)
  • Puzzel met het laten vallen van eieren
  • Probleem met woordbreuk
  • Vertex Cover-probleem
  • Probleem met het stapelen van tegels
  • Probleem met het stapelen van dozen
  • Partitie probleem
  • Handelsreiziger Probleem | Set 1 (naïeve en dynamische programmering)
  • Langste palindrome vervolgreeks
  • Langste gemeenschappelijke toenemende deelreeks (LCS + LIS)
  • Zoek alle afzonderlijke subset- (of subreeks-)sommen van een array
  • Gewogen taakplanning
  • Tel verstoringen (permutatie zodat geen enkel element in de oorspronkelijke positie verschijnt)
  • Minimale inserties om een ​​palindroom te vormen
  • Matching van jokertekenpatronen
  • Manieren om ballen zo te rangschikken dat aangrenzende ballen van verschillende typen zijn

3. Moeilijke problemen bij dynamisch programmeren (DP)

  • Palindroompartitionering
  • Probleem met woordomloop
  • Het scheidingsprobleem van de schilder
  • Programma voor Bridge en Torch-probleem
  • Vermenigvuldiging van matrixketens
  • Het afdrukken van haakjes in het probleem van de matrixketenvermenigvuldiging
  • Maximale somrechthoek in een 2D-matrix
  • Maximale winst door maximaal k keer een aandeel te kopen en verkopen
  • Minimale kosten voor het sorteren van tekenreeksen met behulp van omkeerbewerkingen van verschillende kosten
  • Aantal AP-subreeksen (rekenkundige progressie) in een array
  • Inleiding tot dynamisch programmeren op bomen
  • Maximale boomhoogte wanneer een knooppunt als root kan worden beschouwd
  • De langste herhalende en niet-overlappende subtekenreeks

Snelle links:

  • Leer datastructuur en algoritmen | DSA-zelfstudie
  • Top 20 interviewvragen voor dynamisch programmeren
  • ‘Oefenproblemen’ over dynamisch programmeren
  • ‘Quiz’ over dynamisch programmeren