Dynamisk programmering är en metod som används inom matematik och datavetenskap för att lösa komplexa problem genom att bryta ner dem i enklare delproblem. Genom att lösa varje delproblem endast en gång och lagra resultaten undviker det redundanta beräkningar, vilket leder till effektivare lösningar för ett brett spektrum av problem. Den här artikeln ger en detaljerad utforskning av dynamiska programmeringskoncept, illustrerad med exempel.

prime ingen kod i java

Dynamisk programmering

Innehållsförteckning

• Vad är dynamisk programmering?
• Hur fungerar dynamisk programmering?
• Exempel på dynamisk programmering
• När ska man använda dynamisk programmering?
• Metoder för dynamisk programmering
• Dynamisk programmeringsalgoritm
• Fördelar med dynamisk programmering
• Tillämpningar av dynamisk programmering
• Lär dig grundläggande dynamisk programmering
• Avancerade koncept inom dynamisk programmering
• Dynamiska programmeringsproblem

Vad är dynamisk programmering (DP)?

Dynamisk programmering (DP) är en metod som används inom matematik och datavetenskap för att lösa komplexa problem genom att bryta ner dem i enklare delproblem. Genom att lösa varje delproblem endast en gång och lagra resultaten undviker det redundanta beräkningar, vilket leder till effektivare lösningar för ett brett spektrum av problem.

Hur fungerar dynamisk programmering (DP)?

• Identifiera underproblem: Dela upp huvudproblemet i mindre, oberoende delproblem.
• Butikslösningar: Lös varje delproblem och lagra lösningen i en tabell eller array.
• Bygg upp lösningar: Använd de lagrade lösningarna för att bygga upp lösningen på huvudproblemet.
• Undvik redundans: Genom att lagra lösningar säkerställer DP att varje delproblem endast löses en gång, vilket minskar beräkningstiden.

Exempel på dynamisk programmering (DP)

Exempel 1: Tänk på problemet med att hitta Fibonacci-sekvensen:

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

Brute Force Approach:

För att hitta det n:te Fibonacci-numret med ett brute force-tillvägagångssätt, skulle du helt enkelt lägga till (n-1):e och (n-2):e Fibonacci-siffror. Detta skulle fungera, men det skulle vara ineffektivt för stora värden på n , eftersom det skulle kräva beräkning av alla tidigare Fibonacci-tal.

Dynamisk programmeringsmetod:

Fibonacci-serien med dynamisk programmering

• Underproblem: F(0), F(1), F(2), F(3), …
• Butikslösningar: Skapa en tabell för att lagra värdena för F(n) när de beräknas.
• Bygg upp lösningar: För F(n), slå upp F(n-1) och F(n-2) i tabellen och lägg till dem.
• Undvik redundans: Tabellen säkerställer att varje delproblem (t.ex. F(2)) endast löses en gång.

Genom att använda DP kan vi effektivt beräkna Fibonacci-sekvensen utan att behöva räkna om delproblem.

lär dig noggrannhetspoäng

Exempel 2: Längsta gemensamma undersekvens (att hitta den längsta undersekvensen som är gemensam för två strängar)

Exempel 3: Kortaste vägen i en graf (att hitta den kortaste vägen mellan två noder i en graf)

Exempel 4: Ryggsäcksproblem (att hitta det maximala värdet av föremål som kan placeras i en ryggsäck med en given kapacitet)

När ska man använda dynamisk programmering (DP)?

Dynamisk programmering är en optimeringsteknik som används för att lösa problem som består av följande egenskaper:

1. Optimal understruktur:

Optimal understruktur innebär att vi kombinerar de optimala resultaten av delproblem för att uppnå det optimala resultatet av det större problemet.

java int till char

Exempel:

Tänk på problemet med att hitta lägsta kostnad väg i en viktad graf från en källa nod till a destination nod. Vi kan dela upp det här problemet i mindre delproblem:

• Hitta minimum kosta väg från källa nod till var och en mellanliggande nod.
• Hitta minimum kosta väg från var och en mellanliggande nod till destination nod.

Lösningen på det större problemet (att hitta minimikostnadsvägen från källnoden till destinationsnoden) kan konstrueras från lösningarna på dessa mindre delproblem.

2. Överlappande delproblem:

Samma delproblem löses upprepade gånger i olika delar av problemet.

Exempel:

Tänk på problemet med att beräkna Fibonacci-serien . För att beräkna Fibonacci-talet vid index n , måste vi beräkna Fibonacci-talen vid index n-1 och n-2 . Detta innebär att underproblemet att beräkna Fibonacci-numret vid index n-1 används två gånger i lösningen på det större problemet med att beräkna Fibonacci-talet vid index n .

Tillvägagångssätt för dynamisk programmering (DP)

Dynamisk programmering kan uppnås med två metoder:

1. Uppifrån och ned tillvägagångssätt (memoisering):

I top-down-metoden, även känd som memoisering , börjar vi med den slutliga lösningen och delar upp den rekursivt i mindre delproblem. För att undvika överflödiga beräkningar lagrar vi resultaten av lösta delproblem i en memoiseringstabell.

Låt oss dela upp uppifrån och ned tillvägagångssätt:

• Börjar med den slutliga lösningen och bryter rekursivt ner den i mindre delproblem.
• Lagrar lösningarna på delproblem i en tabell för att undvika överflödiga beräkningar.
• Lämplig när antalet delproblem är stort och många av dem återanvänds.

2. Bottom-up-metoden (tabell):

I bottom-up-metoden, även känd som tabulering , vi börjar med de minsta delproblemen och bygger gradvis upp till den slutliga lösningen. Vi lagrar resultaten av lösta delproblem i en tabell för att undvika överflödiga beräkningar.

Låt oss dela upp Bottom-up-metoden:

• Börjar med de minsta delproblemen och bygger gradvis upp till den slutliga lösningen.
• Fyller en tabell med lösningar på delproblem på ett bottom-up-sätt.
• Lämplig när antalet delproblem är litet och den optimala lösningen direkt kan beräknas från lösningarna till mindre delproblem.

Dynamisk programmering (DP) Algoritm

Dynamisk programmering är en algoritmisk teknik som löser komplexa problem genom att dela upp dem i mindre delproblem och lagra deras lösningar för framtida bruk. Det är särskilt effektivt för problem som innehåller överlappande delproblem och optimal understruktur.

Vanliga algoritmer som använder dynamisk programmering:

• Longest Common Subsequence (LCS): Hittar den längsta gemensamma undersekvensen mellan två strängar.
• Kortaste vägen i en graf: Hittar den kortaste vägen mellan två noder i en graf.
• Knapsäcksproblem: Bestämmer det maximala värdet av föremål som kan placeras i en ryggsäck med en given kapacitet.
• Matriskedjemultiplikation: Optimerar ordningen för matrismultiplikation för att minimera antalet operationer.
• Fibonacci-sekvens: Beräknar det n:te Fibonacci-talet.

Fördelar med dynamisk programmering (DP)

Dynamisk programmering har en lång rad fördelar, inklusive:

arraylist och länkad lista

• Undviker att räkna om samma delproblem flera gånger, vilket leder till betydande tidsbesparingar.
• Säkerställer att den optimala lösningen hittas genom att överväga alla möjliga kombinationer.
• Bryter ner komplexa problem i mindre, mer hanterbara delproblem.

Tillämpningar av dynamisk programmering (DP)

Dynamisk programmering har ett brett utbud av applikationer, inklusive:

• Optimering: Knapsäcksproblem, problem med kortaste vägen, problem med maximal subarray
• Datavetenskap: Längsta gemensamma undersekvens, redigera avstånd, strängmatchning
• Operationsforskning: Lagerhantering, schemaläggning, resursallokering

Låt oss nu utforska en omfattande färdplan för att behärska dynamisk programmering.

Lär dig grunderna i dynamisk programmering (DP)

• Vad är memoisering? En komplett handledning
• Tabulering vs Memoisering
• Optimal underbyggnadsfastighet
• Egenskap för överlappande delproblem
• Hur löser man ett dynamiskt programmeringsproblem?

• Fibonacci-siffror
• n:e katalanska numret
• Bell Numbers (Antal sätt att partitionera en uppsättning)
• Binomial koefficient
• Myntbyteproblem
• Delmängd Summa Problem
• Beräkna nCr % p
• Att skära en stav
• Måla staket Algoritm
• Längsta vanliga efterföljd
• Längst ökande efterföljd
• Längsta efterföljd så att skillnaden mellan angränsande är en
• Maximal storlek kvadratisk submatris med alla 1:or
• Min kostnadsväg
• Minsta antal hopp för att nå slutet
• Längsta gemensamma delsträng (rymdoptimerad DP-lösning)
• Räkna sätt att nå den n:e trappan med steg 1, 2 eller 3
• Räkna alla möjliga vägar från övre vänster till nedre höger i en mXn-matris
• Unika vägar i ett rutnät med hinder

2. Medelstora problem med dynamisk programmering (DP)

• Floyd Warshall-algoritm
• Bellman–Ford Algoritm
• 0-1 Knapsäcksproblem
• Utskrift av föremål i 0/1 ryggsäck
• Obegränsad ryggsäck (upprepning av föremål tillåts)
• Ägg tappa pussel
• Word Break problem
• Vertex Cover Problem
• Problem med kakelstapling
• Problem med lådstapling
• Partitionsproblem
• Resande säljare problem | Set 1 (naiv och dynamisk programmering)
• Längsta palindromisk efterföljd
• Längsta vanliga ökande följdsekvens (LCS + LIS)
• Hitta alla distinkta delmängder (eller delsekvens) summor av en matris
• Viktad jobbschemaläggning
• Räkna avvikelser (Permutation så att inget element visas i sin ursprungliga position)
• Minsta insättningar för att bilda ett palindrom
• Matchning av jokertecken
• Sätt att arrangera bollar så att intilliggande bollar är av olika typer

3. Svåra problem med dynamisk programmering (DP)

• Palindromuppdelning
• Ordbrytningsproblem
• Målarens partitionsproblem
• Program för problem med bro och ficklampa
• Matrix Kedjemultiplikation
• Skriva ut parenteser i Matrix Chain Multiplication Problem
• Maximal summarektangel i en 2D-matris
• Maximal vinst genom att köpa och sälja en aktie högst k gånger
• Minsta kostnad för att sortera strängar med hjälp av återföringsoperationer av olika kostnader
• Count of AP (Aritmetic Progression) Subsekvenser i en array
• Introduktion till dynamisk programmering på träd
• Maximal höjd på träd när någon nod kan betraktas som rot
• Längsta repeterande och icke-överlappande delsträng

Snabblänkar:

• Lär dig datastruktur och algoritmer | Handledning för DSA
• De 20 bästa intervjufrågorna för dynamisk programmering
• 'Övningsproblem' på dynamisk programmering
• 'Frågesport' om dynamisk programmering