Dynamisch programmeren: voorbeelden, veelvoorkomende problemen en oplossingen

Het lijdt geen twijfel dat dynamische programmeerproblemen erg intimiderend kunnen zijn in een coderingsinterview. Zelfs als je misschien weet dat een probleem moet worden opgelost met behulp van een dynamische programmeermethode, is het een uitdaging om binnen een beperkt tijdsbestek met een werkende oplossing te komen.

De beste manier om goed te zijn in dynamische programmeerproblemen, is door er zoveel mogelijk door te nemen. Hoewel u niet per se de oplossing voor elk probleem hoeft te onthouden, is het goed om een ​​idee te hebben hoe u er een kunt implementeren.

Wat is dynamisch programmeren?

Simpel gezegd, dynamisch programmeren is een optimalisatiemethode voor recursieve algoritmen, waarvan de meeste worden gebruikt om computer- of wiskundige problemen op te lossen.

Je kunt het ook een algoritmische techniek noemen om een ​​optimalisatieprobleem op te lossen door het op te splitsen in eenvoudigere deelproblemen. Een sleutelprincipe waarop dynamisch programmeren is gebaseerd, is dat de optimale oplossing voor een probleem afhangt van de oplossingen voor de deelproblemen.

Overal waar we een recursieve oplossing zien die herhaalde oproepen voor dezelfde invoer heeft, kunnen we deze optimaliseren met behulp van dynamische programmering. Het idee is om de resultaten van subproblemen eenvoudig op te slaan, zodat we ze later niet opnieuw hoeven te berekenen.

Dynamisch geprogrammeerde oplossingen hebben een veeltermcomplexiteit die een veel snellere looptijd verzekert dan andere technieken zoals recursie of backtracking. In de meeste gevallen vermindert dynamisch programmeren de tijdcomplexiteit, ook wel bekend als big-O, van exponentieel naar polynoom.

Wat is Big-O-notatie?

Je code moet efficiënt zijn, maar hoe laat je zien hoe efficiënt iets is? Met Big-O!

Nu u een goed idee heeft van wat dynamisch programmeren is, is het tijd om een ​​paar veelvoorkomende problemen en hun oplossingen te bekijken.

Dynamische programmeerproblemen

1. Knapzak probleem

Probleemstelling

Gegeven een set items, elk met een gewicht en een waarde, bepaal dan het aantal items dat moet worden opgenomen in een verzameling zodat het totale gewicht een bepaalde limiet niet overschrijdt en de totale waarde zo groot is als mogelijk.

U krijgt twee integer-arrays waarden [0..n-1] en gewichten [0..n-1] die waarden en gewichten vertegenwoordigen die zijn gekoppeld aan respectievelijk n items. Ook gegeven is een geheel getal W. wat de capaciteit van de rugzak vertegenwoordigt.

Hier lossen we het 0/1 knapzakprobleem op, wat betekent dat we ervoor kunnen kiezen om een ​​item toe te voegen of het uit te sluiten.

Algoritme

• Maak een tweedimensionale array met n + 1 rijen en w + 1 kolommen. Een rijnummer n geeft de set items aan van 1 tot ik, en een kolomnummer w geeft het maximale draagvermogen van de tas aan.
• De numerieke waarde op [i] [j] geeft de totale waarde van items tot ik in een tas die een maximaal gewicht van j kan dragen.
• Op elke coördinaat [i] [j] Kies in de array de maximale waarde die we zonder kunnen verkrijgen item i, of de maximale waarde die we kunnen verkrijgen item iwelke groter is.
• De maximaal verkrijgbare waarde door item i op te nemen is de som van item ik zichzelf en de maximale waarde die kan worden verkregen met de resterende capaciteit van de knapzak.
• Voer deze stap uit totdat u de maximale waarde voor het W.^th rij.

Code

def FindMax (W, n, waarden, gewichten):
MaxVals = [[0 voor x in bereik (W + 1)] voor x in bereik (n + 1)]
voor i in bereik (n + 1):
voor w in bereik (W + 1):
als i == 0 of w == 0:
MaxVals [i] [w] = 0
elif gewichten [i-1] <= w:
MaxVals [i] [w] = max (waarden [i-1]
+ MaxVals [i-1] [w-gewichten [i-1]], 
MaxVals [i-1] [w])
anders:
MaxVals [i] [w] = MaxVals [i-1] [w]
retourneer MaxVals [n] [W]

2. Probleem met het wisselen van munten

Probleemstelling

Stel dat u een reeks getallen krijgt die de waarden van elke munt vertegenwoordigen. Zoek bij een bepaald bedrag het minimum aantal munten dat nodig is om dat bedrag te verdienen.

Algoritme

• Initialiseer een reeks grootte n + 1, waarbij n het bedrag is. Initialiseer de waarde van elke index ik in de array om gelijk te zijn aan het bedrag. Dit geeft het maximale aantal munten aan (met munten van denominatie 1) dat nodig is om dat bedrag te verdienen.
• Aangezien er geen denominatie is voor 0, initialiseert u het basisscenario waar matrix [0] = 0.
• Voor elke andere index ik, vergelijken we de waarde erin (die aanvankelijk is ingesteld op n + 1) met de waarde matrix [i-k] +1, waar k is minder dan ik. Dit controleert in wezen de hele reeks tot i-1 om het minimaal mogelijke aantal munten te vinden dat we kunnen gebruiken.
• Als de waarde een matrix [i-k] + 1 is lager dan de bestaande waarde bij array [i], vervangt u de waarde bij array [i] met die van matrix [i-k] +1.

Code

def coin_change (d, amount, k):
nummers = [0] * (aantal + 1)
voor j in bereik (1, aantal + 1):
minimum = bedrag
voor i in bereik (1, k + 1):
if (j> = d [i]):
minimum = min (minimum, 1 + cijfers [j-d [i]])
nummers [j] = minimum
retournummers [bedrag]

3. Fibonacci

Probleemstelling

De Fibonacci-reeks is een reeks gehele getallen waarbij het volgende gehele getal in de reeks de som is van de vorige twee.

Het wordt gedefinieerd door de volgende recursieve relatie: F (0) = 0, F (n) = F (n-1) + F (n-2), waar F (n) is dan^th termijn. In deze opgave moeten we alle getallen in een Fibonacci-reeks genereren tot een bepaalde n^th termijn.

Algoritme

• Gebruik eerst een recursieve benadering om de gegeven herhalingsrelatie te implementeren.
• Om dit probleem recursief op te lossen, moet het afbreken F (n) in F (n-1) + F (n-2), en vervolgens de functie aanroepen met F (n-1) en F (n + 2) als parameters. We doen dit tot in de basisgevallen n = 0, of n = 1 zijn bereikt.
• Nu gebruiken we een techniek die memoisatie wordt genoemd. Sla de resultaten van alle functieaanroepen op in een array. Dit zorgt ervoor dat voor elke n, F (n) hoeft maar één keer te worden berekend.
• Voor alle volgende berekeningen kan de waarde ervan eenvoudig in constante tijd uit de array worden opgehaald.

Code

def fibonacci (n): 
fibNums = [0, 1] 
voor i in bereik (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
retourneer fibNums [n] 

4. Langst toenemende opvolging

Probleemstelling

Zoek de lengte van de langste toenemende subreeks binnen een gegeven array. De langste toenemende subreeks is een subreeks binnen een reeks getallen met oplopende volgorde. De nummers binnen de subreeks moeten uniek zijn en in oplopende volgorde.

Ook hoeven de items van de reeks niet opeenvolgend te zijn.

Algoritme

• Begin met een recursieve benadering waarbij u de waarde van de langst toenemende subreeks van elke mogelijke subarray van index nul tot index i, waarbij i kleiner is dan of gelijk is aan de grootte van de array.
• Om van deze methode een dynamische methode te maken, maakt u een array om de waarde voor elke subreeks op te slaan. Initialiseer alle waarden van deze array op 0.
• Elke index ik van deze reeks komt overeen met de lengte van de langste toenemende subreeks voor een subreeks van grootte ik.
• Nu, voor elke recursieve aanroep van findLIS (arr, n), controleer de n^th index van de array. Als deze waarde 0 is, berekent u de waarde met behulp van de methode in de eerste stap en slaat u deze op de n^th inhoudsopgave.
• Retourneer ten slotte de maximale waarde uit de array. Dit is de lengte van de langste toenemende subreeks van een bepaalde grootte n.

Code

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
voor i in bereik (1, n):
voor j in bereik (0, i):
als myArray [i]> myArray [j] en lis [i] lis [i] = lis [j] +1
maxVal = 0
voor i in bereik (n):
maxVal = max (maxVal, lis [i])
retourneer maxVal

Oplossingen voor dynamische programmeerproblemen

Nu u enkele van de meest populaire problemen met dynamisch programmeren heeft doorlopen, is het tijd om de oplossingen zelf te implementeren. Als je vastloopt, kun je altijd terugkomen en het algoritme-gedeelte voor elk probleem hierboven raadplegen.

Gezien hoe populaire technieken zoals recursie en dynamisch programmeren tegenwoordig zijn, kan het geen kwaad om enkele populaire platforms te bekijken waar u dergelijke concepten en Verbeter uw codeervaardigheden. Hoewel u deze problemen misschien niet dagelijks tegenkomt, zult u ze zeker tegenkomen in een technisch interview.

Uiteraard zal het hebben van de knowhow van veelvoorkomende problemen zijn vruchten afwerpen wanneer u voor uw volgende sollicitatiegesprek gaat. Dus open je favoriete IDE, en ga aan de slag!

De 9 beste YouTube-kanalen met code om te leren programmeren

Klaar om te beginnen met coderen? Deze YouTube-kanalen zijn een geweldige manier om aan de slag te gaan met game-, app-, web- en andere ontwikkeling.

Over de auteur