Drumuri unice într-o grilă
Până acum tabelul DP a fost o listă simplă. Multe probleme de interviu au însă două dimensiuni: o grilă, două texte, obiecte și capacitate. Începem cu cea mai simplă: un robot de depozit care merge doar la dreapta sau în jos. Câte drumuri diferite are?
Problema
Un robot pornește din colțul stânga-sus al unui depozit cu r rânduri și c coloane și trebuie să ajungă în colțul dreapta-jos. La fiecare pas merge o celulă la dreapta sau în jos. Câte drumuri distincte există?
Scrie drumuri(r, c) (numărul de drumuri într-o grilă r × c, doar dreapta și jos) și drumuri_obstacole(grila) (aceeași problemă, 1 = obstacol), ambele cu un tabel DP pe două dimensiuni. Testele sunt deja scrise.
- Creează tabelul cu [[...] * c for _ in range(r)].
- Completează dp[i][j] din celula de sus și din cea din stânga.
- La obstacole, celula blocată are 0 drumuri. Trebuie să apară: 28, 3, 2, 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan