Dynamisk programmering: exempel, vanliga problem och lösningar

Det råder ingen tvekan om att dynamiska programmeringsproblem kan vara mycket skrämmande i en kodningsintervju. Även när du kanske vet att ett problem måste lösas med en dynamisk programmeringsmetod är det en utmaning att kunna komma på en fungerande lösning inom en begränsad tidsram.

Det bästa sättet att bli bra på dynamiska programmeringsproblem är att gå igenom så många av dem du kan. Även om du inte nödvändigtvis behöver memorera lösningen på varje problem, är det bra att ha en idé om hur du ska gå tillväga för att implementera ett.

Vad är dynamisk programmering?

Enkelt uttryckt är dynamisk programmering en optimeringsmetod för rekursiva algoritmer, varav de flesta används för att lösa beräknings- eller matematiska problem.

Du kan också kalla det en algoritmisk teknik för att lösa ett optimeringsproblem genom att dela upp det i enklare delproblem. En nyckelprincip som dynamisk programmering bygger på är att den optimala lösningen på ett problem beror på lösningarna på dess delproblem.

Varhelst vi ser en rekursiv lösning som har upprepade anrop för samma ingångar, kan vi optimera den med dynamisk programmering. Tanken är att helt enkelt lagra resultaten av delproblem så att vi inte behöver räkna om dem vid behov senare.

Dynamiskt programmerade lösningar har en polynom komplexitet som säkerställer en mycket snabbare körtid än andra tekniker som rekursion eller backtracking. I de flesta fall reducerar dynamisk programmering tidskomplexiteten, även känd som big-O, från exponentiell till polynom.

Nu när du har en bra uppfattning om vad dynamisk programmering är, är det dags att kolla in några vanliga problem och deras lösningar.

Dynamiska programmeringsproblem

1. Knapsäcksproblem

Problembeskrivning

Givet en uppsättning artiklar, var och en med en vikt och ett värde, bestäm antalet av varje objekt som ska inkluderas i en samling så att den totala vikten inte överstiger en given gräns och det totala värdet är så stort som möjligt.

Du får två heltalsmatriser värden[0..n-1] och vikter[0..n-1] som representerar värden och vikter associerade med n respektive objekt. Ett heltal anges också W som representerar ryggsäckens kapacitet.

Här löser vi 0/1 ryggsäcksproblemet, vilket innebär att vi kan välja att antingen lägga till en vara eller utesluta den.

Algoritm

Skapa en tvådimensionell array med n+1 rader och w+1 kolumner. Ett radnummer n betecknar uppsättningen objekt från 1 till ioch ett kolumnnummer w anger väskans maximala bärkapacitet. Det numeriska värdet vid [i][j] anger det totala värdet av föremål fram till i i en väska som kan bära en maxvikt på j. Vid varje koordinat [i][j] i arrayen väljer du det maximala värdet som vi kan få utan punkt i, eller det maximala värdet som vi kan få med punkt i— beroende på vilket som är störst. Det maximala värdet som kan erhållas genom att inkludera artikel i är summan av artikel i sig själv och det maximala värde som kan erhållas med ryggsäckens återstående kapacitet. Utför detta steg tills du hittar det maximala värdet för Wraden.

Koda

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. Myntbyteproblem

Problembeskrivning

Anta att du får en uppsättning siffror som representerar värdena på varje mynt. Givet ett specifikt belopp, hitta det minsta antal mynt som behövs för att göra det beloppet.

Algoritm

Initiera en array av storlek n+1, där n är mängden. Initiera värdet på varje index i i arrayen för att vara lika med mängden. Detta anger det maximala antalet mynt (med mynt av valör 1) som krävs för att täcka det beloppet. Eftersom det inte finns någon valör för 0, initiera basfallet där array[0] = 0. För vartannat index i, jämför vi värdet i den (som initialt är inställd på n+1) med värdet array[i-k] +1, var k är mindre än i. Detta kontrollerar i huvudsak hela arrayen fram till i-1 för att hitta det minsta möjliga antalet mynt vi kan använda. Om värdet som helst array[i-k] + 1 är lägre än det befintliga värdet på array[i], ersätt värdet vid array[i] med den kl array[i-k] +1.

Koda

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[j-d[i]])
numbers[j] = minimum





	



	



	



	



return numbers[amount]

3. Fibonacci

Problembeskrivning

Fibonacci-serien är en sekvens av heltal där nästa heltal i serien är summan av de två föregående.

Det definieras av följande rekursiva relation: F(0) = 0, F(n) = F(n-1) + F(n-2), var F(n) är den n:e termen. I det här problemet måste vi generera alla siffror i en Fibonacci-sekvens fram till en given n:e term.

Algoritm

Använd först ett rekursivt tillvägagångssätt för att implementera den givna återfallsrelationen. Att rekursivt lösa detta problem innebär att bryta ner F(n) in i F(n-1) + F(n-2), och sedan anropa funktionen med F(n-1) och F(n+2) som parametrar. Vi gör detta tills basfallen där n = 0, eller n = 1 nås. Nu använder vi en teknik som kallas memoization. Lagra resultatet av alla funktionsanrop i en array. Detta kommer att säkerställa att för varje n, F(n) behöver bara beräknas en gång. För eventuella efterföljande beräkningar kan dess värde helt enkelt hämtas från matrisen i konstant tid.

Koda

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. Längst ökande efterföljd

Problembeskrivning

Hitta längden på den längst ökande undersekvensen i en given array. Den längst ökande delsekvensen är en delsekvens inom en array av tal med en ökande ordning. Numren i undersekvensen måste vara unika och i stigande ordning.

Objekten i sekvensen behöver inte heller vara i följd.

Algoritm

Börja med ett rekursivt tillvägagångssätt där du beräknar värdet av den längst ökande undersekvensen av varje möjlig delmatris från index noll till index i, där i är mindre än eller lika med storleken på arrayen. För att göra den här metoden till en dynamisk, skapa en array för att lagra värdet för varje undersekvens. Initiera alla värden för denna array till 0. Varje index i av denna array motsvarar längden av den längst ökande undersekvensen för en undergrupp av storlek i. Nu, för varje rekursivt samtal av hittaLIS(arr, n), kontrollera narrayens index. Om detta värde är 0, beräkna sedan värdet med metoden i det första steget och lagra det på nindex. Slutligen, returnera det maximala värdet från arrayen. Detta är längden på den längst ökande undersekvensen av en given storlek n.

Koda

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

Lösningar på problem med dynamisk programmering

Nu när du har gått igenom några av de mest populära dynamiska programmeringsproblemen är det dags att försöka implementera lösningarna själv. Om du har fastnat kan du alltid komma tillbaka och hänvisa till algoritmavsnittet för varje problem ovan.

Med tanke på hur populära tekniker som rekursion och dynamisk programmering är idag, kommer det inte skada att kolla in några populära plattformar där du kan lära dig sådana koncept och finslipa dina kodningsfärdigheter. Även om du kanske inte stöter på dessa problem dagligen, kommer du säkert att stöta på dem i en teknisk intervju.

Naturligtvis kommer det att ge utdelning när du går på din nästa intervju att ha kunskap om vanliga problem. Så öppna upp din favorit-IDE och kom igång!

Om författaren

Yash Chellani (10 publicerade artiklar)

Yash är en blivande datavetenskapsstudent som älskar att bygga saker och skriva om allt som är tekniskt. I hans free tid, han gillar att spela squash, läsa en kopia av den senaste Murakami och jaga drakar i Skyrim.

Mer från Yash Chellani

Prenumerera på vårt nyhetsbrev

Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!

Klicka här för att prenumerera