Dynamisk programmering er en metode som brukes i matematikk og informatikk for å løse komplekse problemer ved å bryte dem ned i enklere delproblemer. Ved å løse hvert delproblem bare én gang og lagre resultatene, unngår det overflødige beregninger, noe som fører til mer effektive løsninger for et bredt spekter av problemer. Denne artikkelen gir en detaljert utforskning av dynamiske programmeringskonsepter, illustrert med eksempler.

kontroll strukturer python

Dynamisk programmering

Innholdsfortegnelse

• Hva er dynamisk programmering?
• Hvordan fungerer dynamisk programmering?
• Eksempler på dynamisk programmering
• Når skal man bruke dynamisk programmering?
• Tilnærminger til dynamisk programmering
• Dynamisk programmeringsalgoritme
• Fordeler med dynamisk programmering
• Anvendelser av dynamisk programmering
• Lær grunnleggende om dynamisk programmering
• Avanserte konsepter innen dynamisk programmering
• Dynamiske programmeringsproblemer

Hva er dynamisk programmering (DP)?

Dynamisk programmering (DP) er en metode som brukes i matematikk og informatikk for å løse komplekse problemer ved å bryte dem ned i enklere delproblemer. Ved å løse hvert delproblem bare én gang og lagre resultatene, unngår det overflødige beregninger, noe som fører til mer effektive løsninger for et bredt spekter av problemer.

Hvordan fungerer dynamisk programmering (DP)?

• Identifiser underproblemer: Del opp hovedproblemet i mindre, uavhengige delproblemer.
• Butikkløsninger: Løs hvert delproblem og lagre løsningen i en tabell eller matrise.
• Bygg opp løsninger: Bruk de lagrede løsningene til å bygge opp løsningen på hovedproblemet.
• Unngå redundans: Ved å lagre løsninger sikrer DP at hvert delproblem bare løses én gang, noe som reduserer beregningstiden.

Eksempler på dynamisk programmering (DP)

Eksempel 1: Tenk på problemet med å finne Fibonacci-sekvensen:

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

Brute Force-tilnærming:

For å finne det n-te Fibonacci-tallet ved å bruke en brute force-tilnærming, legger du ganske enkelt til (n-1)th og (n-2)th Fibonacci tall. Dette ville fungere, men det ville være ineffektivt for store verdier av n , da det ville kreve å beregne alle de tidligere Fibonacci-tallene.

Dynamisk programmeringsmetode:

Fibonacci-serien bruker dynamisk programmering

• Underproblemer: F(0), F(1), F(2), F(3), …
• Butikkløsninger: Lag en tabell for å lagre verdiene til F(n) slik de beregnes.
• Bygg opp løsninger: For F(n), slå opp F(n-1) og F(n-2) i tabellen og legg dem til.
• Unngå redundans: Tabellen sikrer at hvert delproblem (f.eks. F(2)) bare løses én gang.

Ved å bruke DP kan vi effektivt beregne Fibonacci-sekvensen uten å måtte beregne delproblemer på nytt.

if else-setning i java

Eksempel 2: Lengste felles undersekvens (finne den lengste undersekvensen som er felles for to strenger)

Eksempel 3: Korteste vei i en graf (finne den korteste veien mellom to noder i en graf)

Eksempel 4: Ryggsekkproblem (finne den maksimale verdien av gjenstander som kan plasseres i en ryggsekk med en gitt kapasitet)

Når skal man bruke dynamisk programmering (DP)?

Dynamisk programmering er en optimaliseringsteknikk som brukes ved løsning av problemer som består av følgende egenskaper:

1. Optimal understruktur:

Optimal understruktur betyr at vi kombinerer de optimale resultatene av delproblemer for å oppnå det optimale resultatet av det større problemet.

hvordan bryte ut av en while loop java

Eksempel:

Vurder problemet med å finne minimumskostnad bane i en vektet graf fra en kilde node til a mål node. Vi kan dele dette problemet ned i mindre delproblemer:

• Finn minimum koste sti fra kilde node til hver mellomliggende node.
• Finn minimum koste vei fra hver mellomliggende node til mål node.

Løsningen på det større problemet (finne minimumskostnadsbanen fra kildenoden til destinasjonsnoden) kan konstrueres fra løsningene til disse mindre delproblemene.

2. Overlappende underproblemer:

De samme delproblemene løses gjentatte ganger i ulike deler av oppgaven.

Eksempel:

Vurder problemet med å beregne Fibonacci-serien . For å beregne Fibonacci-tallet ved indeks n , må vi beregne Fibonacci-tallene ved indekser n-1 og n-2 . Dette betyr at underproblemet med å beregne Fibonacci-tallet ved indeks n-1 brukes to ganger i løsningen på det større problemet med å beregne Fibonacci-tallet ved indeks n .

Tilnærminger til dynamisk programmering (DP)

Dynamisk programmering kan oppnås ved hjelp av to tilnærminger:

1. Top-down-tilnærming (memoisering):

I top-down-tilnærmingen, også kjent som memoisering , starter vi med den endelige løsningen og bryter den rekursivt ned i mindre delproblemer. For å unngå overflødige beregninger lagrer vi resultatene av løste deloppgaver i en memoiseringstabell.

La oss analysere ovenfra og ned-tilnærming:

• Starter med den endelige løsningen og bryter den rekursivt ned i mindre delproblemer.
• Lagrer løsningene på delproblemer i en tabell for å unngå overflødige beregninger.
• Egnet når antallet delproblemer er stort og mange av dem gjenbrukes.

2. Bottom-up-tilnærming (tabell):

I bottom-up-tilnærmingen, også kjent som tabulering , starter vi med de minste delproblemene og bygger oss gradvis opp til den endelige løsningen. Vi lagrer resultatene av løste deloppgaver i en tabell for å unngå overflødige beregninger.

intelligent idé vs formørkelse

La oss analysere nedenfra og opp-tilnærming:

• Starter med de minste delproblemene og bygger seg gradvis opp til den endelige løsningen.
• Fyller en tabell med løsninger på delproblemer på en nedenfra og opp-måte.
• Egnet når antallet delproblemer er lite og den optimale løsningen kan beregnes direkte fra løsningene til mindre delproblemer.

Dynamisk programmering (DP) Algoritme

Dynamisk programmering er en algoritmisk teknikk som løser komplekse problemer ved å bryte dem ned i mindre delproblemer og lagre deres løsninger for fremtidig bruk. Det er spesielt effektivt for problemer som inneholder overlappende delproblemer og optimal underbygning.

Vanlige algoritmer som bruker dynamisk programmering:

• Lengste felles sekvens (LCS): Finner den lengste felles undersekvensen mellom to strenger.
• Korteste vei i en graf: Finner den korteste veien mellom to noder i en graf.
• Rullesekkproblem: Bestemmer den maksimale verdien av gjenstander som kan plasseres i en ryggsekk med en gitt kapasitet.
• Matrisekjedemultiplikasjon: Optimaliserer rekkefølgen av matrisemultiplikasjon for å minimere antall operasjoner.
• Fibonacci-sekvens: Beregner det n-te Fibonacci-tallet.

Fordeler med dynamisk programmering (DP)

Dynamisk programmering har en lang rekke fordeler, inkludert:

• Unngår å omberegne de samme delproblemene flere ganger, noe som fører til betydelige tidsbesparelser.
• Sikrer at den optimale løsningen blir funnet ved å vurdere alle mulige kombinasjoner.
• Bryter ned komplekse problemer i mindre, mer håndterbare delproblemer.

Anvendelser av dynamisk programmering (DP)

Dynamisk programmering har et bredt spekter av bruksområder, inkludert:

• Optimalisering: Rullesekkproblem, problem med korteste vei, problem med maksimal undergruppe
• Datavitenskap: Lengste felles undersekvens, rediger avstand, strengmatching
• Driftsforskning: Lagerstyring, planlegging, ressursallokering

La oss nå utforske et omfattende veikart for å mestre dynamisk programmering.

Lær grunnleggende om dynamisk programmering (DP)

• Hva er memoarisering? En komplett opplæring
• Tabulering vs Memoisering
• Optimal underbygningseiendom
• Overlappende underproblemer Egenskap
• Hvordan løser jeg et dynamisk programmeringsproblem?

• Fibonacci tall
• n. katalansk nummer
• Bell Numbers (antall måter å partisjonere et sett på)
• Binomial koeffisient
• Myntbytteproblem
• Delmengde Sum Problem
• Beregn nCr % p
• Kutte en stang
• Algoritme for maling av gjerde
• Lengste vanlige etterfølge
• Lengst økende etterfølge
• Lengste undersekvens slik at forskjellen mellom tilstøtende er én
• Maksimal størrelse kvadratisk undermatrise med alle 1-er
• Min kostnadsbane
• Minimum antall hopp for å nå slutten
• Lengste felles understreng (romoptimalisert DP-løsning)
• Tell måter å nå den n'te trappen ved å bruke trinn 1, 2 eller 3
• Tell alle mulige baner fra øverst til venstre til nederst til høyre i en mXn-matrise
• Unike stier i et rutenett med hindringer

2. Middels problemer med dynamisk programmering (DP)

• Floyd Warshall-algoritme
• Bellman–Ford-algoritme
• 0-1 Rullesekkproblem
• Utskrift av varer i 0/1 ryggsekk
• Ubegrenset ryggsekk (gjentakelse av varer tillatt)
• Egg slippe puslespill
• Word Break Problem
• Vertex Cover Problem
• Problem med flisstabling
• Problem med eskestabling
• Partisjonsproblem
• Reisende selgerproblem | Sett 1 (naiv og dynamisk programmering)
• Lengste palindromiske sekvens
• Lengste vanlige økende sekvens (LCS + LIS)
• Finn alle distinkte delmengde (eller delsekvens) summer av en matrise
• Vektet jobbplanlegging
• Count Derangements (Permutasjon slik at ingen elementer vises i sin opprinnelige posisjon)
• Minimumsinnsettinger for å danne et palindrom
• Matching med jokertegn
• Måter å arrangere baller slik at tilstøtende baller er av forskjellige typer

3. Harde problemer med dynamisk programmering (DP)

• Palindrom-partisjonering
• Ordbrytingsproblem
• Malerens partisjonsproblem
• Program for Bridge and Torch-problem
• Matrisekjedemultiplikasjon
• Skrive ut parentes i Matrix Chain Multiplication Problem
• Maksimalt sumrektangel i en 2D-matrise
• Maksimal fortjeneste ved å kjøpe og selge en aksje på det meste k ganger
• Minimumskostnad for å sortere strenger ved å bruke reverseringsoperasjoner av forskjellige kostnader
• Antall AP (aritmetisk progresjon) undersekvenser i en matrise
• Introduksjon til dynamisk programmering på trær
• Maksimal høyde på treet når en hvilken som helst node kan betraktes som rot
• Lengste repeterende og ikke-overlappende delstreng

Hurtigkoblinger:

• Lær datastruktur og algoritmer | DSA veiledning
• Topp 20 dynamisk programmeringsintervjuspørsmål
• 'Øvningsproblemer' på dynamisk programmering
• 'Quiz' om dynamisk programmering