Dynamisk programmering er en metode, der bruges i matematik og datalogi til at løse komplekse problemer ved at opdele dem i enklere delopgaver. Ved kun at løse hvert delproblem én gang og gemme resultaterne, undgår det overflødige beregninger, hvilket fører til mere effektive løsninger på en lang række problemer. Denne artikel giver en detaljeret udforskning af dynamiske programmeringskoncepter, illustreret med eksempler.
powershell admin
Dynamisk programmering
Indholdsfortegnelse
- Hvad er dynamisk programmering?
- Hvordan fungerer dynamisk programmering?
- Eksempler på dynamisk programmering
- Hvornår skal man bruge dynamisk programmering?
- Tilgange til dynamisk programmering
- Dynamisk programmeringsalgoritme
- Fordele ved dynamisk programmering
- Anvendelser af dynamisk programmering
- Lær grundlæggende om dynamisk programmering
- Avancerede koncepter i dynamisk programmering
- Dynamiske programmeringsproblemer
Hvad er dynamisk programmering (DP)?
Dynamisk programmering (DP) er en metode, der bruges i matematik og datalogi til at løse komplekse problemer ved at opdele dem i enklere delopgaver. Ved kun at løse hvert delproblem én gang og gemme resultaterne, undgår det overflødige beregninger, hvilket fører til mere effektive løsninger på en lang række problemer.
Hvordan fungerer dynamisk programmering (DP)?
- Identificer underproblemer: Opdel hovedproblemet i mindre, selvstændige underopgaver.
- Butiksløsninger: Løs hvert underproblem og gem løsningen i en tabel eller et array.
- Opbygningsløsninger: Brug de gemte løsninger til at opbygge løsningen på hovedproblemet.
- Undgå redundans: Ved at gemme løsninger sikrer DP, at hvert delproblem kun løses én gang, hvilket reducerer beregningstiden.
Eksempler på dynamisk programmering (DP)
Eksempel 1: Overvej problemet med at finde Fibonacci-sekvensen:
Fibonacci sekvens: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Brute Force tilgang:
For at finde det n'te Fibonacci-tal ved hjælp af en brute force-tilgang, tilføjer du blot (n-1)th og (n-2)th Fibonacci-tal. Dette ville virke, men det ville være ineffektivt for store værdier af n , da det ville kræve at beregne alle de tidligere Fibonacci-tal.
Dynamisk programmeringstilgang:
Fibonacci-serien ved hjælp af dynamisk programmering
- Underproblemer: F(0), F(1), F(2), F(3), …
- Butiksløsninger: Opret en tabel for at gemme værdierne af F(n), som de beregnes.
- Opbygningsløsninger: For F(n), slå F(n-1) og F(n-2) op i tabellen og tilføj dem.
- Undgå redundans: Tabellen sikrer, at hvert delproblem (f.eks. F(2)) kun løses én gang.
Ved at bruge DP kan vi effektivt beregne Fibonacci-sekvensen uden at skulle genberegne underproblemer.
if else sætning i java
Eksempel 2: Længste fælles undersekvens (finde den længste undersekvens, der er fælles for to strenge)
Eksempel 3: Korteste vej i en graf (finde den korteste vej mellem to noder i en graf)
Eksempel 4: Rulleproblem (finde den maksimale værdi af genstande, der kan placeres i en rygsæk med en given kapacitet)
Hvornår skal man bruge dynamisk programmering (DP)?
Dynamisk programmering er en optimeringsteknik, der bruges til at løse problemer, og som består af følgende egenskaber:
1. Optimal underbygning:
Optimal understruktur betyder, at vi kombinerer de optimale resultater af delproblemer for at opnå det optimale resultat af det større problem.
java retur array
Eksempel:
Overvej problemet med at finde minimumsomkostninger sti i en vægtet graf fra en kilde node til en bestemmelsessted node. Vi kan opdele dette problem i mindre underproblemer:
- Find minimum koste vej fra kilde node til hver mellemliggende node.
- Find minimum koste vej fra hver mellemliggende node til bestemmelsessted node.
Løsningen på det større problem (at finde den mindste omkostningsvej fra kildenoden til destinationsknuden) kan konstrueres ud fra løsningerne på disse mindre underproblemer.
2. Overlappende underproblemer:
De samme delproblemer løses gentagne gange i forskellige dele af problemet.
Eksempel:
Overvej problemet med at beregne Fibonacci-serien . For at beregne Fibonacci-tallet ved indeks n , skal vi beregne Fibonacci-tallene ved indekser n-1 og n-2 . Dette betyder, at underproblemet med at beregne Fibonacci-tallet ved indeks n-1 bruges to gange i løsningen af det større problem med at beregne Fibonacci-tallet ved indeks n .
Metoder til dynamisk programmering (DP)
Dynamisk programmering kan opnås ved hjælp af to tilgange:
1. Top-down tilgang (memoisering):
I top-down tilgang, også kendt som huskes , starter vi med den endelige løsning og opdeler den rekursivt i mindre delproblemer. For at undgå overflødige beregninger gemmer vi resultaterne af løste delopgaver i en husketabel.
Lad os opdele Top-down tilgang:
- Starter med den endelige løsning og opdeler den rekursivt i mindre delproblemer.
- Gemmer løsningerne til delproblemer i en tabel for at undgå overflødige beregninger.
- Velegnet når antallet af delproblemer er stort og mange af dem genbruges.
2. Bottom-up tilgang (tabel):
I bottom-up tilgangen, også kendt som tabulering , starter vi med de mindste delproblemer og bygger gradvist op til den endelige løsning. Vi gemmer resultaterne af løste delopgaver i en tabel for at undgå overflødige beregninger.
java boolesk streng
Lad os opdele Bottom-up tilgang:
- Starter med de mindste delproblemer og bygger gradvist op til den endelige løsning.
- Fylder en tabel med løsninger på delproblemer på en bottom-up måde.
- Velegnet når antallet af delproblemer er lille, og den optimale løsning kan beregnes direkte fra løsningerne til mindre delproblemer.
Dynamisk programmering (DP) Algoritme
Dynamisk programmering er en algoritmisk teknik, der løser komplekse problemer ved at opdele dem i mindre delproblemer og gemme deres løsninger til fremtidig brug. Det er især effektivt til problemer, der indeholder overlappende delproblemer og optimal underbygning.
Almindelige algoritmer, der bruger dynamisk programmering:
- Længste fælles sekvens (LCS): Finder den længste fælles undersekvens mellem to strenge.
- Korteste vej i en graf: Finder den korteste vej mellem to noder i en graf.
- Rullesæk problem: Bestemmer den maksimale værdi af genstande, der kan placeres i en rygsæk med en given kapacitet.
- Matrix kæde multiplikation: Optimerer rækkefølgen af matrixmultiplikation for at minimere antallet af operationer.
- Fibonacci-sekvens: Beregner det n'te Fibonacci-tal.
Fordele ved dynamisk programmering (DP)
Dynamisk programmering har en lang række fordele, herunder:
- Undgår at genberegne de samme underproblemer flere gange, hvilket fører til betydelige tidsbesparelser.
- Sikrer at den optimale løsning findes ved at overveje alle mulige kombinationer.
- Opdeler komplekse problemer i mindre, mere overskuelige delproblemer.
Anvendelser af dynamisk programmering (DP)
Dynamisk programmering har en bred vifte af applikationer, herunder:
- Optimering: Rullesæk problem, korteste vej problem, maksimal subarray problem
- Computer videnskab: Længste fælles undersekvens, redigeringsafstand, strengmatchning
- Operationsforskning: Lagerstyring, planlægning, ressourceallokering
Lad os nu udforske en omfattende køreplan for at mestre dynamisk programmering.
Lær grundlæggende om dynamisk programmering (DP)
- Hvad er huskeseddel? En komplet tutorial
- Tabulering vs Memoisering
- Optimal underbygningsejendom
- Overlappende underproblemer egenskab
- Hvordan løser man et dynamisk programmeringsproblem?
Avancerede koncepter i dynamisk programmering (DP)
- Bitmasking og dynamisk programmering | Sæt 1
- Bitmasking og dynamisk programmering | Sæt-2 (TSP)
- Ciffer DP | Introduktion
- Sum over delmængder | Dynamisk programmering
Dynamisk programmering (DP) Problemer
Vi har klassificeret standard dynamisk programmering (DP) problemer i tre kategorier: Let, Medium og Hard.
1. Lette problemer med dynamisk programmering (DP)
- Fibonacci-tal
- n. catalansk nummer
- Klokkenumre (antal måder at opdele et sæt på)
- Binomial koefficient
- Møntskifteproblem
- Subset Sum Problem
- Beregn nCr % p
- Skæring af en stang
- Algorithme for maling af hegn
- Længste fælles efterfølger
- Længst stigende efterfølger
- Længste efterfølge, sådan at forskellen mellem tilstødende er én
- Maksimal størrelse kvadratisk undermatrix med alle 1'ere
- Min omkostningssti
- Minimum antal hop for at nå slutningen
- Længste fælles understreng (rumoptimeret DP-løsning)
- Tæl måder at nå den n'te trappe ved at bruge trin 1, 2 eller 3
- Tæl alle mulige stier fra øverst til venstre til nederst til højre i en mXn-matrix
- Unikke stier i et gitter med forhindringer
2. Mellemstore problemer med dynamisk programmering (DP)
- Floyd Warshall algoritme
- Bellman-Ford algoritme
- 0-1 Rullesæk Problem
- Udskrivning af varer i 0/1 Rullesæk
- Ubundet rygsæk (gentagelse af varer tilladt)
- Puslespil til at tabe æg
- Word Break problem
- Vertex Cover Problem
- Problem med flisestabling
- Box-stabling problem
- Partitionsproblem
- Rejsende sælger problem | Sæt 1 (naiv og dynamisk programmering)
- Længste palindromiske efterfølger
- Længste almindelig stigende sekvens (LCS + LIS)
- Find alle distinkte delmængde (eller delsekvens) summer af en matrix
- Vægtet jobplanlægning
- Count Derangements (Permutation sådan, at intet element vises i dets oprindelige position)
- Minimum indsættelser for at danne et palindrom
- Matching af wildcard-mønster
- Måder at arrangere bolde sådan, at tilstødende bolde er af forskellige typer
3. Hårde problemer med dynamisk programmering (DP)
- Palindromopdeling
- Ordombrydningsproblem
- Malerens skillevægsproblem
- Program til problemer med bro og fakkel
- Matrix kæde multiplikation
- Udskrivning af parenteser i Matrix Chain Multiplication Problem
- Maksimalt sum rektangel i en 2D matrix
- Maksimal fortjeneste ved at købe og sælge en aktie højst k gange
- Minimumsomkostninger til at sortere strenge ved hjælp af tilbageførselsoperationer af forskellige omkostninger
- Antal AP (Aritmetic Progression) Subsekvenser i en matrix
- Introduktion til dynamisk programmering på træer
- Maksimal højde på træet, når enhver knude kan betragtes som rod
- Længste gentagne og ikke-overlappende understreng
Hurtige links:
- Lær datastruktur og algoritmer | DSA Tutorial
- Top 20 interviewspørgsmål til dynamisk programmering
- 'Practice Problemer' om dynamisk programmering
- 'Quiz' om dynamisk programmering