Programare dinamica

1. Dată fiind o număr întreg n, returnează un array ans de lungime n + 1 astfel încât pentru
fiecare i (0 <= i <= n), ans[i] este numărul de 1 în reprezentarea binară a lui i.
Orice număr i este obținut prin adăugarea unui bit la dreapta unui număr mai mic (i >> 1).
Dacă știm câți 1 sunt în i >> 1, putem afla câți sunt în i prin simpla adunare cu i & 1.
Reprezentarea binară a unui număr poate fi privită ca fiind formată din:
• un bit în plus față de un număr mai mic,
• sau o repetare a unei structuri deja cunoscute.

Caz de baza
Pentru i = 0: ans[0]=0 deoarece binar 0 este 0, care are zero biți de 1.

Relatia de recurenta
Pentru orice i ≥ 1: ans[i]=ans[i//2]+(i%2)
care este echivalent cu: ans[i]=ans[i>>1]+(i&1)

Exemplu complet pentru n=5

ans[0]=0(caz de baza)
ans[1]=ans[0]+1=0+1=1
ans[2]=ans[1]+0=1+0=1
ans[3]=ans[1]+1=1+1=2
ans[4]=ans[2]+0=1+0=1
ans[5]=ans[2]+1=1+1=2

2. Având un număr întreg numRows, returnează primele numRows din triunghiul lui Pascal.
Caz de baza
Rândul 0: [1]
Rândul 1: [1, 1]
Rândul 2: [1, 2, 1]
Rândul 3: [1, 3, 3, 1]

Relatia de recurenta
Elementul de pe poziția j din rândul i este:
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i – 1][j], 1 <= j < i

3. Având două șiruri de caractere s și t, returnează true dacă s este o subsecvență a lui t, sau
false în caz contrar. O subsecvență a unui șir de caractere este un șir nou format din șirul original
prin ștergerea unor caractere (poate fi niciunul) fără a modifica pozițiile relative ale caracterelor
rămase. (De exemplu, „ace” este o subsecvență a „abcde”, în timp ce „aec” nu este).
Verificăm dacă s este subsecvență a lui t folosind programare dinamică:
• Construim o matrice booleeană dp, unde:
• dp[i][j] = True dacă prefixul s[0..i-1] este subsecvență a lui t[0..j-1].
Caz de baza
1. s este șir vid (s = "")
• Atunci "" este subsecvență a oricărui șir t.
• Deci pentru orice j, dp[0][j] = True.
 2. t este șir vid dar s ≠ ""
• Nu putem obține caractere din nimic.
• Deci pentru orice i > 0, dp[i][0] = False.

Relatia de recurenta
Pentru i ≥ 1 și j ≥ 1:
• Dacă s[i-1] == t[j-1], atunci:
dp[i][j]=dp[i−1][j−1]
• Altfel:dp[i][j]=dp[i][j−1]

4. Cel mai lung subsir care este palindrom

Cazuri de bază:
1. Subșiruri de lungime 1:
◦ Orice caracter de sine stătător este un palindrom.
◦ Deci: dp[i][i]=True ∀i
2. Subșiruri de lungime 2:
◦ Dacă două caractere consecutive sunt egale, atunci subșirul este palindrom.
◦ Deci: dp[i][i+1]=(s[i]==s[i+1])

Relatia de recurenta
Pentru subșiruri de lungime ≥ 3: dp[i][j]=(s[i]==s[j])∧dp[i+1][j−1]

5. Având n perechi de paranteze, scrieți o funcție care să genereze toate combinațiile de

paranteze bine formate.
Cazuri de bază:
• n=3 → ["((()))","(()())","(())()","()(())","()()()"]
• n=1 → ["()"]

sol(n)= i=0⋃n−1("("+sol(i)+")"+sol(n−1−i))
Relatia de recurenta

6. Având o grilă m x n umplută cu numere nenegative, găsiți o cale de la stânga sus la

dreapta jos, care minimizează suma tuturor numerelor de-a lungul acestei căi.

Cazuri de bază:
n=2 → matrice 2x2 => 1 1 / 2 1 → pornim din punctul 1 si alegem valoarea minima
dintre 1 sau 2 care este 1, si apoi alegem 1 si => 1 + 1 + 1 = 3 suma minima
n=3 → matrice 3x3 => 1 3 1/1 5 1/4 2 1 → pornim din punctul 1
si alegem la dreapta 3 apoi la dreapta 1, in jos 1 si iar in jos 1 => 1+3+1+1+1= 7 suma minima

Relatia de recurenta
sum = min(d[i][j+1], d[i+1][j]) + d[i][j]
 7. Vi se oferă un tablou de numere întregi nums. Inițial, vă aflați la primul indice al
tabloului, iar fiecare element din tablou reprezintă lungimea maximă a saltului dvs. în acea poziție.
Returnați true dacă puteți ajunge la ultimul indice, sau false în caz contrar.

Cazuri de baza
dp[i] = True dacă poziția i este accesibilă de la poziția 0

Relatia de recurenta
S={s1, s2, …, sn}, si∈N, n>0
dp[i] = j=0Σi-1 (dp[j] ^ j + nums[j] >=i)

8. Având două șiruri de caractere word1 și word2, returnează numărul minim de operații
necesare pentru a converti word1 în word2. Ai la dispoziție următoarele trei operații permise asupra
unui cuvânt:
Inserează un caracter
Șterge un caracter
Înlocuiește un caracter

Cazuri de baza
Dacă word1 este gol (i = 0), atunci trebuie inserate toate caracterele din word2: dp[0][j]=j
Dacă word2 este gol (j = 0), atunci trebuie șterse toate caracterele din word1: dp[i][0]=i

Relatia de recurenta
Pentru i > 0 și j > 0:
• Dacă word1[i-1] == word2[j-1] (ultimele caractere coincid), atunci nu facem nicio operație:
dp[i][j]=dp[i−1][j−1]
• Dacă word1[i-1] ≠ word2[j-1], alegem operația cu cost minim dintre:
1. Insert (inserăm word2[j-1]): dp[i][j−1]+1
2. Delete (ștergem word1[i-1]): dp[i−1][j]+1
3. Replace (înlocuim word1[i-1] cu word2[j-1]): dp[i−1][j−1]+1

• Deci: dp[i][j]=min(dp[i][j−1]+1,dp[i−1][j]+1,dp[i−1][j−1]+1)

9. Ați interceptat un mesaj secret codificat sub forma unui șir de numere. Mesajul este
decodificat prin următoarea corespondență:
„1” -> „A” | „2” -> „B”… | „25” -> „Y” | „26” -> „Z”
Cu toate acestea, în timp ce decodificați mesajul, vă dați seama că există multe moduri
diferite de a decodifica mesajul, deoarece unele coduri sunt conținute în alte coduri („2” și „5” față
de „25”).
De exemplu, „11106” poate fi decodificat în:
„AAJF” cu gruparea (1, 1, 10, 6)
„KJF” cu gruparea (11, 10, 6)
Gruparea (1, 11, 06) este invalidă, deoarece „06” nu este un cod valid (numai „6” este valid).
Notă: pot exista șiruri imposibil de decodat.
 Având un șir s care conține numai cifre, returnează numărul de moduri în care poate fi
decodat. Dacă întregul șir nu poate fi decodat în niciun mod valid, returnează 0. Cazurile de testare
sunt generate astfel încât răspunsul să încapă într-un întreg de 32 de biți.

Cazuri de baza
Fie dp[i] = numărul de moduri de a decoda prefixul de lungime i (primele i caractere din s).
1. dp[0] = 1 – există exact 1 mod de a decoda șirul gol: fără nicio decodare.
2. dp[1] = 1 dacă primul caracter nu este „0”, altfel dp[1] = 0.

Relatia de recurenta
Dacă s[i-1] ∈ ['1'..'9'], adică NU e '0': dp[i]+=dp[i−1]
Dacă s[i-2:i] ∈ ['10'..'26']: dp[i]+=dp[i−2]

10. Având șirurile s1, s2 și s3, determinați dacă s3 este format prin intercalarea șirurilor s1 și s2. O
intercalare a două șiruri s și t este o configurație în care s și t sunt împărțite în n și m respectiv,
astfel încât:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
Împletirea este s1 + t1 + s2 + t2 + s3 + t3 + ... sau t1 + s1 + t2 + s2 + t3 + s3 + ...
Notă: a + b este concatenarea șirurilor a și b.

Cazuri de baza
Fie dp[i][j] = True dacă prefixul de lungime i din s1 și j din s2 pot forma prefixul de lungime
i + j din s3.

• dp[0][0] = True → șirurile goale formează un alt șir gol.

• dp[i][0] = True dacă s1[:i] == s3[:i]
• dp[0][j] = True dacă s2[:j] == s3[:j]

Relatia de recurenta:
dp[i][j] = (
(dp[i-1][j] and s1[i-1] == s3[i+j-1]) -- dacă folosim un caracter din s1 or
(dp[i][j-1] and s2[j-1] == s3[i+j-1]) -- dacă folosim un caracter din s2
)
11. Având un șir s, împărțiți s astfel încât fiecare parte a împărțirii să fie un palindrom. Returnați
toate împărțirile posibile ale lui s care sunt palindrome.

Cazuri de baza
Fie dp[i][j] = True dacă s[i..j] este un palindrom
dp[i][i] = True # orice caracter singur e palindrom
dp[i][i+1] = (s[i] == s[i+1]) # două caractere sunt palindrom dacă sunt egale

Relatia de recurenta
dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
12. Având un șir s și un dicționar de șiruri wordDict, returnează true dacă s poate fi segmentat într-o
secvență separată prin spații de unul sau mai multe cuvinte din dicționar. Rețineți că același cuvânt
din dicționar poate fi reutilizat de mai multe ori în segmentare.

Cazuri de baza
dp[i] = True dacă `s[0:i]` poate fi împărțit în cuvinte din `wordDict`
dp[0] = True # Șirul vid poate fi segmentat

Relatia de recurenta
dp[j] == True și s[j:i] ∈ wordDict

13. Având un tablou de numere întregi nums, găsiți un subtablou care are cel mai mare produs și
returnați produsul. Cazurile de testare sunt generate astfel încât răspunsul să încapă într-un număr
întreg de 32 de biți.

Cazuri de baza
max_prod[0] = nums[0]
min_prod[0] = nums[0]
rezultat_max = nums[0]

Relatia de recurenta
max_prod[i] = max(nums[i], nums[i] * max_prod[i-1], nums[i] * min_prod[i-1])
min_prod[i] = min(nums[i], nums[i] * max_prod[i-1], nums[i] * min_prod[i-1])
rezultat_max = max(rezultat_max, max_prod[i])

14. Având o matrice binară m x n completată cu 0 și 1, găsiți cel mai mare pătrat care conține numai
1 și returnați aria acestuia.

Cazuri de baza
dp[i][j] = latura celui mai mare pătrat care are colțul dreapta-jos în (i, j).
• Dacă matrix[i][j] == '1' și suntem pe prima linie sau prima coloană (i == 0 sau j ==
0), atunci dp[i][j] = 1
• Dacă matrix[i][j] == '0', atunci dp[i][j] = 0
Relatia de recurenta
• daca matrix[i][j] == 1 => dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
• daca matrix[i][j] == 0 => dp[i][j] = 0
• max_side = max(max_side, dp[i][j])

15. Dată fiind o număr întreg n, returnează cel mai mic număr de numere pătrate perfecte care
însumează n. Un pătrat perfect este un număr întreg care este pătratul unui număr întreg; cu alte
cuvinte, este produsul unui număr întreg cu el însuși. De exemplu, 1, 4, 9 și 16 sunt pătrate perfecte,
în timp ce 3 și 11 nu sunt.
Cazuri de baza
Daca n = 0 => sigurul patrat perfect = 0 este 0 => dp[i] = 0
Relatia de recurenta
dp[i] = numărul minim de pătrate perfecte care însumează i
dp[i] = min(dp[i], dp[i - j*j] + 1) pentru toate j unde j*j ≤ i