[canonical]: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-056

> Pagina completă: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-056
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Model Preadmitere Politehnica București · Informatică #056

10 grile din Programare dinamică, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul Preadmitere Politehnica București

## Teaser gratuit, fără cont

1. Care dintre următoarele afirmații descrie corect tehnica memoizării, folosită în programarea dinamică?

a) Rezultatul fiecărei subprobleme se memorează la prima calculare și se refolosește la apelurile următoare, evitând recalcularea.
b) Subproblemele se rezolvă în ordine aleatorie, iar rezultatul final este media rezultatelor parțiale.
c) Se împarte problema în două jumătăți independente, care se rezolvă recursiv și se combină.
d) Se generează toate soluțiile posibile și se reține cea mai bună dintre ele.
e) La fiecare pas se alege soluția care pare cea mai bună local, fără a reveni asupra alegerii.

Răspuns corect: a) Rezultatul fiecărei subprobleme se memorează la prima calculare și se refolosește la apelurile următoare, evitând recalcularea.

Memoizarea combină recursivitatea cu un tablou de rezultate deja calculate; astfel subproblemele care se suprapun se rezolvă o singură dată. Împărțirea în jumătăți independente este divide et impera, generarea tuturor soluțiilor este forța brută, iar alegerea local optimă fără revenire este metoda greedy.

2. `d[i]` reprezintă numărul de moduri în care se poate urca o scară cu `i` trepte, dacă la fiecare pas se urcă una sau două trepte. Ce se afișează?

a) `55`
b) `34`
c) `21`
d) `256`

Răspuns corect: b) `34`

Ultimul pas urcă $1$ sau $2$ trepte, deci $d[i]=d[i-1]+d[i-2]$: $1,2,3,5,8,13,21,34$.

3. Care este lungimea celui mai lung subșir strict crescător al șirului $3,1,4,1,5,9,2,6$? (Elementele subșirului nu trebuie să fie consecutive în șir.)

a) $3$
b) $5$
c) $4$
d) $6$

Răspuns corect: c) $4$

Fie $L[i]$ lungimea celui mai lung subșir strict crescător care se termină pe poziția $i$: $L=1,1,2,1,3,4,2,4$ (de exemplu $1,4,5,9$ sau $1,4,5,6$). Maximul este $4$.

4. `d[i][j]` reprezintă numărul de drumuri de la colțul $(1,1)$ la celula $(i,j)$ a unui tablou, deplasându-se doar în jos sau la dreapta. Ce se afișează?

a) `35`
b) `20`
c) `70`
d) `21`

Răspuns corect: a) `35`

În celula $(i,j)$ se poate ajunge doar din $(i-1,j)$ sau $(i,j-1)$. Un drum până la $(4,5)$ are $3$ pași în jos și $4$ la dreapta, în orice ordine: $\binom{7}{3}=35$.

5. Tabloul `m` memorează valorile monedelor disponibile (în număr nelimitat), iar `d[s]` este numărul minim de monede cu care se poate plăti suma `s`. Ce se afișează?

a) `10`
b) `2`
c) `3`
d) `5`
e) `4`

Răspuns corect: c) `3`

$d[s]$ se obține adăugând o monedă la cea mai bună soluție pentru $s-m[k]$. Suma $10$ nu se poate plăti cu $2$ monede ($4+4=8$, $4+3=7$), dar se poate cu $3$: $3+3+4$.