Programare dinamică este o metodă folosită în matematică și informatică pentru a rezolva probleme complexe prin descompunerea lor în subprobleme mai simple. Rezolvând fiecare subproblemă o singură dată și stocând rezultatele, se evită calculele redundante, ducând la soluții mai eficiente pentru o gamă largă de probleme. Acest articol oferă o explorare detaliată a conceptelor de programare dinamică, ilustrată cu exemple.

idee intellij vs eclipsă

Programare dinamică

Cuprins

• Ce este programarea dinamică?
• Cum funcționează programarea dinamică?
• Exemple de programare dinamică
• Când să folosiți programarea dinamică?
• Abordări ale programării dinamice
• Algoritm de programare dinamică
• Avantajele programării dinamice
• Aplicatii ale programarii dinamice
• Aflați elementele de bază ale programării dinamice
• Concepte avansate în programarea dinamică
• Probleme de programare dinamică

Ce este programarea dinamică (DP)?

Programare dinamică (DP) este o metodă folosită în matematică și informatică pentru a rezolva probleme complexe prin descompunerea lor în subprobleme mai simple. Rezolvând fiecare subproblemă o singură dată și stocând rezultatele, se evită calculele redundante, ducând la soluții mai eficiente pentru o gamă largă de probleme.

Cum funcționează programarea dinamică (DP)?

• Identificați subproblemele: Împărțiți problema principală în subprobleme mai mici, independente.
• Soluții pentru magazin: Rezolvați fiecare subproblemă și stocați soluția într-un tabel sau o matrice.
• Construiți soluții: Utilizați soluțiile stocate pentru a construi soluția la problema principală.
• Evitați redundanța: Prin stocarea soluțiilor, DP se asigură că fiecare subproblemă este rezolvată o singură dată, reducând timpul de calcul.

Exemple de programare dinamică (DP)

Exemplul 1: Luați în considerare problema găsirii șirului Fibonacci:

Secvența Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Abordarea forței brute:

Pentru a găsi al n-lea număr Fibonacci folosind o abordare de forță brută, ați adăuga pur și simplu (n-1)-a și (n-2)-a numerele Fibonacci. Acest lucru ar funcționa, dar ar fi ineficient pentru valori mari de n , deoarece ar necesita calcularea tuturor numerelor Fibonacci anterioare.

Abordare de programare dinamică:

Seria Fibonacci folosind programarea dinamică

• Subprobleme: F(0), F(1), F(2), F(3), …
• Soluții pentru magazin: Creați un tabel pentru a stoca valorile lui F(n) pe măsură ce sunt calculate.
• Construiți soluții: Pentru F(n), căutați F(n-1) și F(n-2) în tabel și adăugați-le.
• Evitați redundanța: Tabelul asigură că fiecare subproblemă (de exemplu, F(2)) este rezolvată o singură dată.

Folosind DP, putem calcula eficient secvența Fibonacci fără a fi nevoie să recalculăm subprobleme.

cum să accesezi fotografiile icloud

Exemplul 2: Cea mai lungă subsecvență comună (găsește cea mai lungă subsecvență comună pentru două șiruri)

Exemplul 3: Cea mai scurtă cale dintr-un grafic (găsește cea mai scurtă cale între două noduri dintr-un grafic)

Exemplul 4: Problemă rucsac (găsirea valorii maxime a articolelor care pot fi plasate într-un rucsac cu o anumită capacitate)

Când să folosiți programarea dinamică (DP)?

Programarea dinamică este o tehnică de optimizare utilizată la rezolvarea problemelor care constă din următoarele caracteristici:

1. Substructură optimă:

Substructura optimă înseamnă că combinăm rezultatele optime ale subproblemelor pentru a obține rezultatul optim al problemei mai mari.

data java la șir

Exemplu:

Luați în considerare problema găsirii cost minim calea într-un grafic ponderat de la a sursă nod la a destinaţie nodul. Putem descompune această problemă în subprobleme mai mici:

• Găsi minim cost calea de la sursă nod la fiecare intermediar nodul.
• Găsi minim cost cale de la fiecare intermediar nodul la destinaţie nodul.

Soluția problemei mai mari (găsirea căii costului minim de la nodul sursă la nodul destinație) poate fi construită din soluțiile acestor subprobleme mai mici.

2. Subprobleme suprapuse:

Aceleași subprobleme sunt rezolvate în mod repetat în diferite părți ale problemei.

Exemplu:

Luați în considerare problema calculării Seria Fibonacci . Pentru a calcula numărul Fibonacci la index n , trebuie să calculăm numerele Fibonacci la indici n-1 și n-2 . Aceasta înseamnă că subproblema calculării numărului Fibonacci la index n-1 este folosit de două ori în rezolvarea problemei mai mari de calcul a numărului Fibonacci la index n .

Abordări ale programării dinamice (DP)

Programarea dinamică poate fi realizată folosind două abordări:

1. Abordare de sus în jos (memorizare):

În abordarea de sus în jos, cunoscută și ca memorare , începem cu soluția finală și o descompunem recursiv în subprobleme mai mici. Pentru a evita calculele redundante, stocăm rezultatele subproblemelor rezolvate într-un tabel de memorare.

Să defalcăm abordarea de sus în jos:

• Începe cu soluția finală și o descompune recursiv în subprobleme mai mici.
• Stochează soluțiile subproblemelor într-un tabel pentru a evita calculele redundante.
• Potrivit atunci când numărul de subprobleme este mare și multe dintre ele sunt reutilizate.

2. Abordare de jos în sus (tabulare):

În abordarea de jos în sus, cunoscută și ca intabulare , începem cu cele mai mici subprobleme și construim treptat până la soluția finală. Stocăm rezultatele subproblemelor rezolvate într-un tabel pentru a evita calculele redundante.

Să defalcăm abordarea de jos în sus:

• Începe cu cele mai mici subprobleme și se acumulează treptat până la soluția finală.
• Umple un tabel cu soluții la subprobleme într-o manieră de jos în sus.
• Potrivit atunci când numărul de subprobleme este mic și soluția optimă poate fi calculată direct de la soluții la subprobleme mai mici.

Programare dinamică (DP) Algoritm

Programarea dinamică este o tehnică algoritmică care rezolvă probleme complexe, împărțindu-le în subprobleme mai mici și stocând soluțiile lor pentru utilizare ulterioară. Este deosebit de eficient pentru problemele care contine subprobleme suprapuse și substructură optimă.

Algoritmi obișnuiți care utilizează programarea dinamică:

• Cea mai lungă subsecvență comună (LCS): Găsește cea mai lungă subsecvență comună între două șiruri.
• Cea mai scurtă cale dintr-un grafic: Găsește calea cea mai scurtă între două noduri dintr-un grafic.
• Problema la rucsac: Determină valoarea maximă a articolelor care pot fi introduse într-un rucsac cu o anumită capacitate.
• Înmulțirea lanțului de matrice: Optimizează ordinea înmulțirii matricei pentru a minimiza numărul de operații.
• Secvența Fibonacci: Calculează al n-lea număr Fibonacci.

Avantajele programării dinamice (DP)

Programarea dinamică are o gamă largă de avantaje, printre care:

• Evită recalcularea acelorași subprobleme de mai multe ori, ceea ce duce la economii semnificative de timp.
• Se asigură că soluția optimă este găsită luând în considerare toate combinațiile posibile.
• Descompune problemele complexe în subprobleme mai mici și mai ușor de gestionat.

Aplicatii ale programarii dinamice (DP)

Programarea dinamică are o gamă largă de aplicații, inclusiv:

rând vs coloană

• Optimizare: Problemă la rucsac, cea mai scurtă problemă cu calea cea mai scurtă, problema subbary maxim
• Informatică: Cea mai lungă subsecvență comună, distanța de editare, potrivirea șirurilor
• Cercetare operațională: Gestionarea stocurilor, programarea, alocarea resurselor

Acum, să explorăm o foaie de parcurs cuprinzătoare pentru a stăpâni programarea dinamică.

Aflați elementele de bază ale programării dinamice (DP)

• Ce este memorarea? Un tutorial complet
• Tabulare vs memorare
• Proprietatea optimă a substructurii
• Proprietatea Subprobleme suprapuse
• Cum se rezolvă o problemă de programare dinamică?

• numerele Fibonacci
• al n-lea număr catalan
• Numere de clopoțel (număr de moduri de a împărți un set)
• Coeficient binomial
• Problema cu schimbarea monedelor
• Problema sumei subsetului
• Calculați nCr % p
• Tăierea unei tije
• Algoritmul de gard de pictură
• Cea mai lungă subsecvență comună
• Cea mai lungă subsecvență în creștere
• Cea mai lungă succesiune astfel încât diferența dintre adiacenți este de unu
• Dimensiunea maximă a submatricei pătrate cu toate cele 1
• Calea costului minim
• Numărul minim de sărituri pentru a ajunge la capăt
• Cel mai lung subșir comun (soluție DP optimizată pentru spațiu)
• Numărați modalitățile de a ajunge la a n-a treaptă folosind pasul 1, 2 sau 3
• Numărați toate căile posibile de la stânga sus la dreapta jos ale unei matrice mXn
• Căi unice într-o grilă cu obstacole

2. Probleme medii privind programarea dinamică (DP)

• Algoritmul Floyd Warshall
• Algoritmul Bellman-Ford
• 0-1 Problemă la rucsac
• Imprimarea articolelor în rucsac 0/1
• Rucsac nelimitat (repetarea articolelor este permisă)
• Puzzle cu aruncarea ouălor
• Problemă întreruperea cuvântului
• Problemă de acoperire a vârfurilor
• Problemă de stivuire a plăcilor
• Problemă de stivuire a cutiilor
• Problemă de partiție
• Problema vânzătorului călător | Setul 1 (programare naivă și dinamică)
• Cea mai lungă subsecvență palindromică
• Cea mai lungă subsecvență în creștere comună (LCS + LIS)
• Găsiți toate sumele (sau subsecvența) distincte ale unui tablou
• Programare ponderată a locurilor de muncă
• Număr deranjamente (permutare astfel încât niciun element să nu apară în poziția inițială)
• Inserții minime pentru a forma un palindrom
• Potrivirea modelului wildcard
• Modalități de a aranja bilele astfel încât bilele adiacente să fie de diferite tipuri

3. Probleme grele la programarea dinamică (DP)

• Partiționarea palindromului
• Problemă de înfășurare a cuvintelor
• Problema partiției pictorului
• Program pentru problema podului și torței
• Înmulțirea lanțului de matrice
• Imprimarea parantezelor în Problema de multiplicare a lanțului de matrice
• Suma maximă dreptunghi într-o matrice 2D
• Profit maxim prin cumpărarea și vânzarea unei acțiuni de cel mult k ori
• Cost minim pentru sortarea șirurilor folosind operații de inversare a costurilor diferite
• Numărul de subsecvențe AP (Progresie aritmetică) dintr-o matrice
• Introducere în programarea dinamică pe arbori
• Înălțimea maximă a arborelui când orice nod poate fi considerat rădăcină
• Cel mai lung subșir care se repetă și care nu se suprapune

Link-uri rapide:

• Aflați structura datelor și algoritmi | Tutorial DSA
• Top 20 de întrebări la interviu de programare dinamică
• „Probleme de practică” privind programarea dinamică
• „Quiz” despre programarea dinamică