Programare dinamică: exemple, probleme comune și soluții

Nu există nicio îndoială că problemele de programare dinamică pot fi foarte intimidante într-un interviu de codare. Chiar și atunci când știți că o problemă trebuie rezolvată folosind o metodă de programare dinamică, este o provocare să puteți găsi o soluție de lucru într-un interval de timp limitat.

Cel mai bun mod de a fi bun la problemele de programare dinamică este să parcurgi cât de multe dintre ele poți. Deși nu trebuie neapărat să memorați soluția pentru fiecare problemă, este bine să aveți o idee despre cum să implementați una.

Ce este programarea dinamică?

Pur și simplu, programarea dinamică este o metodă de optimizare pentru algoritmi recursivi, dintre care majoritatea sunt folosite pentru rezolvarea problemelor de calcul sau matematice.

De asemenea, o puteți numi o tehnică algoritmică pentru rezolvarea unei probleme de optimizare prin divizarea acesteia în subprobleme mai simple. Un principiu cheie pe care se bazează programarea dinamică este acela că soluția optimă a unei probleme depinde de soluțiile la subproblemele sale.

Oriunde vedem o soluție recursivă care are apeluri repetate pentru aceleași intrări, o putem optimiza folosind programarea dinamică. Ideea este să stocăm pur și simplu rezultatele subproblemelor, astfel încât să nu mai trebuim să le re-calculăm atunci când este nevoie mai târziu.

Soluțiile programate dinamic au o complexitate polinomială care asigură un timp de rulare mult mai rapid decât alte tehnici, cum ar fi recursivitatea sau urmărirea înapoi. În majoritatea cazurilor, programarea dinamică reduce complexitatea timpului, cunoscută și sub numele de mare-O, de la exponențială la polinomială.

Ce este notația Big-O?

Codul dvs. trebuie să fie eficient, dar cum arătați cât de eficient este ceva? Cu Big-O!

Acum, că aveți o idee bună despre ceea ce este programarea dinamică, este timpul să verificați câteva probleme obișnuite și soluțiile lor.

Probleme de programare dinamică

1. Problema rucsacului

Declarație problemă

Având în vedere un set de articole, fiecare cu o greutate și o valoare, determinați numărul fiecărui articol care trebuie inclus în a colectare, astfel încât greutatea totală să nu depășească o anumită limită și valoarea totală să fie la fel de mare ca posibil.

Vi se oferă două matrice întregi valori [0..n-1] și greutăți [0..n-1] care reprezintă valori și greutăți asociate respectiv cu n itemi. De asemenea, este dat un număr întreg W care reprezintă capacitatea rucsacului.

Aici rezolvăm problema rucsacului 0/1, ceea ce înseamnă că putem alege fie să adăugăm un articol, fie să îl excludem.

Algoritm

• Creați un tablou bidimensional cu n + 1 rânduri și w + 1 coloane. Un număr de rând n denotă setul de articole de la 1 la euși un număr de coloană w denotă capacitatea maximă de încărcare a sacului.
• Valoarea numerică la [i] [j] indică valoarea totală a articolelor până la eu într-o pungă care poate transporta o greutate maximă de j.
• La fiecare coordonată [i] [j] în matrice, alegeți valoarea maximă fără care putem obține elementul i, sau valoarea maximă cu care putem obține elementul ioricare dintre acestea este mai mare.
• Valoarea maximă care poate fi obținută prin includerea articolului i este suma articolului eu în sine și valoarea maximă care poate fi obținută cu capacitatea rămasă a rucsacului.
• Efectuați acest pas până când găsiți valoarea maximă pentru W^a rând.

Cod

def FindMax (W, n, valori, greutăți):
MaxVals = [[0 pentru x în interval (W + 1)] pentru x în interval (n + 1)]
pentru i în interval (n + 1):
pentru w în interval (W + 1):
dacă i == 0 sau w == 0:
MaxVals [i] [w] = 0
greutăți elif [i-1] <= w:
MaxVals [i] [w] = max (valori [i-1]
+ MaxVals [i-1] [w-greutăți [i-1]], 
MaxVals [i-1] [w])
altceva:
MaxVals [i] [w] = MaxVals [i-1] [w]
returnează MaxVals [n] [W]

2. Problema schimbării monedei

Declarație problemă

Să presupunem că vi se oferă o serie de numere care reprezintă valorile fiecărei monede. Având în vedere o anumită sumă, găsiți numărul minim de monede necesare pentru a face acea sumă.

Algoritm

• Inițializați o matrice de dimensiuni n + 1, unde n este suma. Inițializați valoarea fiecărui index eu în matrice să fie egală cu suma. Aceasta indică numărul maxim de monede (folosind monedele cu denumirea 1) necesare pentru a compune suma respectivă.
• Deoarece nu există o denumire pentru 0, inițializați cazul de bază unde matrice [0] = 0.
• Pentru fiecare alt index eu, comparăm valoarea din acesta (care este setată inițial la n + 1) cu valoarea matrice [i-k] +1, Unde k e mai puțin decât eu. Aceasta verifică, în esență, întreaga matrice până la i-1 pentru a găsi numărul minim posibil de monede pe care le putem folosi.
• Dacă valoarea la orice matrice [i-k] + 1 este mai mică decât valoarea existentă la matrice [i], înlocuiți valoarea la matrice [i] cu cea de la matrice [i-k] +1.

Cod

def coin_change (d, sumă, k):
numere = [0] * (sumă + 1)
pentru j în interval (1, sumă + 1):
minimum = suma
pentru i în intervalul (1, k + 1):
dacă (j> = d [i]):
minimum = min (minim, 1 + numere [j-d [i]])
numere [j] = minim
returnează numerele [suma]

3. Fibonacci

Declarație problemă

Seria Fibonacci este o succesiune de numere întregi în care următorul număr întreg din serie este suma celor două precedente.

Este definit de următoarea relație recursivă: F (0) = 0, F (n) = F (n-1) + F (n-2), Unde F (n) este atunci^a termen. În această problemă, trebuie să generăm toate numerele dintr-o secvență Fibonacci până la un n dat^a termen.

Algoritm

• În primul rând, utilizați o abordare recursivă pentru a implementa relația de recurență dată.
• Rezolvarea recursivă a acestei probleme implică descompunerea F (n) în F (n-1) + F (n-2), și apoi apelarea funcției cu F (n-1) și F (n + 2) ca parametri. Facem acest lucru până la cazurile de bază în care n = 0, sau n = 1 sunt atinse.
• Acum, folosim o tehnică numită memoizare. Stocați rezultatele tuturor apelurilor de funcții într-o matrice. Acest lucru va asigura că pentru fiecare n, F (n) trebuie calculat o singură dată.
• Pentru orice calcul ulterior, valoarea sa poate fi extrasă pur și simplu din matrice în timp constant.

Cod

def Fibonacci (n): 
fibNums = [0, 1] 
pentru i în intervalul (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
return fibNums [n] 

4. Cea mai lungă creștere ulterioară

Declarație problemă

Găsiți lungimea celei mai lungi subsecvențe în creștere din interiorul unei matrice date. Cea mai lungă subsecvență în creștere este o subsecvență într-o serie de numere cu o ordine crescătoare. Numerele din subsecvență trebuie să fie unice și în ordine crescătoare.

De asemenea, elementele secvenței nu trebuie să fie consecutive.

Algoritm

• Începeți cu o abordare recursivă în care calculați valoarea celei mai lungi subsecvențe în creștere a fiecare subarray posibil de la index zero la index i, unde i este mai mic sau egal cu dimensiunea matrice.
• Pentru a transforma această metodă într-una dinamică, creați o matrice pentru a stoca valoarea pentru fiecare subsecvență. Inițializați toate valorile acestei matrice la 0.
• Fiecare index eu din această matrice corespunde lungimii celei mai lungi subsecvențe în creștere pentru un subarray de dimensiuni eu.
• Acum, pentru fiecare apel recursiv al findLIS (arr, n), verifică n^a indexul matricei. Dacă această valoare este 0, atunci calculați valoarea utilizând metoda din primul pas și stocați-o la n^a index.
• În cele din urmă, returnați valoarea maximă din matrice. Aceasta este lungimea celei mai lungi subsecvențe în creștere a unei dimensiuni date n.

Cod

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
pentru i în intervalul (1, n):
pentru j în intervalul (0, i):
dacă myArray [i]> myArray [j] și lis [i] lis [i] = lis [j] +1
maxVal = 0
pentru i în intervalul (n):
maxVal = max (maxVal, lis [i])
returnează maxVal

Soluții la problemele de programare dinamică

Acum că ați trecut prin unele dintre cele mai populare probleme de programare dinamică, este timpul să încercați să implementați soluțiile de unul singur. Dacă sunteți blocat, puteți reveni oricând și consultați secțiunea algoritmului pentru fiecare problemă de mai sus.

Având în vedere cât de populare sunt tehnicile precum recursivitatea și programarea dinamică astăzi, nu va strica să consultați câteva platforme populare în care puteți învăța astfel de concepte și perfecționează-ți abilitățile de codare. Deși este posibil să nu întâmpinați zilnic aceste probleme, cu siguranță le veți întâlni într-un interviu tehnic.

Bineînțeles, cunoașterea problemelor obișnuite este obligată să plătească dividende atunci când te duci la următorul interviu. Deci, deschide-ți IDE preferatși începeți!

Cele mai bune 9 canale de codare de-a lungul programării YouTube

Sunteți gata să începeți codarea? Aceste canale YouTube sunt o modalitate excelentă de a începe jocurile, aplicațiile, web și alte dezvoltări.

Despre autor