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 fram till en fungerande lösning inom en begränsad tidsram.

Det bästa sättet att vara bra på dynamiska programmeringsproblem är att gå igenom så många av dem som möjligt. Även om du inte nödvändigtvis behöver komma ihåg lösningen på alla problem, är det bra att ha en uppfattning om hur man ska genomföra 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 dator- 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.

Oavsett var vi ser en rekursiv lösning som har upprepade samtal 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 beräkna dem om det behövs senare.

Dynamiskt programmerade lösningar har en polynomkomplexitet som säkerställer en mycket snabbare körtid än andra tekniker som rekursion eller backtracking. I de flesta fall minskar dynamisk programmering tidskomplexitet, även känd som stor-O, från exponential till polynom.

Vad är Big-O-notering?

Din kod måste vara effektiv, men hur visar du hur effektivt något är? Med Big-O!

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. Ryggsäck Problem

Problemförklaring

Med en uppsättning artiklar, var och en med en vikt och ett värde, bestämma antalet för varje artikel som ska ingå i en så att den totala vikten inte överstiger en given gräns och det totala värdet är lika stort som möjlig.

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

Här löser vi 0/1 ryggsäckproblemet, vilket innebär att vi kan välja att antingen lägga till ett objekt eller utesluta det.

Algoritm

• Skapa en tvådimensionell matris 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ärförmåga.
• Det numeriska värdet vid [I j] anger det totala värdet av artiklar fram till i i en väska som kan bära en maximal vikt på j.
• Vid varje koordinat [I j] välj det maximala värdet som vi kan få utan i matrisen artikel i, eller det maximala värdet som vi kan få med artikel idet som är störst.
• Det högsta erhållna värdet genom att inkludera artikel i är summan av artikeln i sig själv och det maximala värdet som kan uppnås med den återstående kapaciteten för ryggsäcken.
• Utför detta steg tills du hittar det maximala värdet för W^th rad.

Koda

def FindMax (W, n, värden, vikter):
MaxVals = [[0 för x inom intervallet (W + 1)] för x inom området (n + 1)]
för i inom intervallet (n + 1):
för w inom intervallet (W + 1):
om jag == 0 eller w == 0:
MaxVals [i] [w] = 0
elif-vikter [i-1] <= w:
MaxVals [i] [w] = max (värden [i-1]
+ MaxVals [i-1] [w-vikter [i-1]], 
MaxVals [i-1] [w])
annan:
MaxVals [i] [w] = MaxVals [i-1] [w]
returnera MaxVals [n] [W]

2. Myntbytesproblem

Problemförklaring

Antag att du får en rad siffror som representerar värdena för varje mynt. Med en viss summa, hitta det minsta antalet mynt som behövs för att göra det beloppet.

Algoritm

• Initiera en rad med storlek n + 1, där n är beloppet. Initiera värdet på varje index i i matrisen för att vara lika med beloppet. Detta anger det maximala antalet mynt (med mynt i benämning 1) som krävs för att kompensera det beloppet.
• Eftersom det inte finns någon beteckning för 0, initialisera basfallet var array [0] = 0.
• För alla andra index i, vi jämför värdet i det (som ursprungligen är inställt på n + 1) med värdet array [i-k] +1, var k är mindre än i. Detta kontrollerar i princip hela matrisen fram till i-1 för att hitta minsta möjliga antal mynt vi kan använda.
• Om värdet på något array [i-k] + 1 är lägre än det befintliga värdet på array [i], byt ut värdet vid array [i] med den på array [i-k] +1.

Koda

def myntbyte (d, belopp, k):
siffror = [0] * (mängd + 1)
för j inom intervallet (1, mängd + 1):
minimum = belopp
för i inom intervallet (1, k + 1):
om (j> = d [i]):
minimum = min (minimum, 1 + siffror [j-d [i]])
siffror [j] = minimum
returnummer [belopp]

3. Fibonacci

Problemförklaring

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 n^th termin. I det här problemet måste vi generera alla siffror i en Fibonacci-sekvens upp till en given n^th termin.

Algoritm

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

Koda

def retracement (n): 
fibNums = [0, 1] 
för i inom intervallet (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
returnera fibNum [n] 

4. Längsta ökande följd

Problemförklaring

Hitta längden på den längst ökande sekvensen i en given matris. Den längst ökande sekvensen är en sekvens inom en rad med siffror med en ökande ordning. Siffrorna i sekvensen måste vara unika och i stigande ordning.

Objekten i sekvensen behöver inte vara konsekutiva.

Algoritm

• Börja med ett rekursivt tillvägagångssätt där du beräknar värdet på den längsta ökande följden av varje möjlig undergrupp från index noll till index i, där i är mindre än eller lika med storleken på array.
• För att göra denna metod till en dynamisk metod, skapa en matris för att lagra värdet för varje efterföljande. Initiera alla värden i denna matris till 0.
• Varje index i av denna matris motsvarar längden på den längsta ökande följden för en subarray av storlek i.
• Nu, för varje rekursivt samtal från findLIS (arr, n), kontrollera n^th index för matrisen. Om detta värde är 0 beräknar du värdet med metoden i det första steget och lagrar det vid n^th index.
• Slutligen, returnera det maximala värdet från matrisen. Detta är längden på den längsta ökande följden av en viss storlek n.

Koda

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
för jag inom intervallet (1, n):
för j inom intervallet (0, i):
om myArray [i]> myArray [j] och lis [i] lis [i] = lis [j] +1
maxVal = 0
för jag inom intervallet (n):
maxVal = max (maxVal, lis [i])
return maxVal

Lösningar på dynamiska programmeringsproblem

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 att skada att kolla in några populära plattformar där du kan lära dig sådana begrepp och finslipa dina kodfä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 är det viktigt att ha kunskapen om vanliga problem att ge utdelning när du går till din nästa intervju. Så öppna upp din favorit IDE, och kom igång!

De 9 bästa kod-längs YouTube-kanalerna för att lära sig programmering

Redo att börja koda? Dessa YouTube-kanaler är ett bra sätt att komma igång inom spel, app, webb och annan utveckling.

Om författaren