Vodič · Algoritmi · Dinamičko programiranje
Dinamičko programiranje – vodič kroz lekcije
Dinamičko programiranje (DP) rešava probleme koji se razlažu na potprobleme koji se ponavljaju: svaki potproblem se reši jednom, rezultat se zapamti i ponovo upotrebi.
Vodič ide od memoizacije do najvažnijih DP obrazaca koji se javljaju na okružnom, državnom i SIO nivou. Rekurzija i bektreking su od sada posebna oblast, sa svojim vodičem.
- 8. razred i srednja škola
- C++
- Priprema za takmičenja
1 Pre dinamičkog programiranja: rekurzija
DP se gradi na rekurziji. Ako ti rekurzija nije jasna, prvo prođi njen vodič.
2 Uvod u dinamičko programiranje
Potproblemi koji se ponavljaju, memoizacija (odozgo nadole) i tabela (odozdo nagore).
3 Osnovni DP obrasci
Tri problema koja se najčešće prepoznaju u takmičarskim zadacima.
4 Napredni DP obrasci
DP nad mrežom, minimalan broj novčića i rastojanje između reči.
DP na mreži (Grid DP)
Putevi i maksimalan zbir kroz matricu.
Otvori lekciju →Problem kusura (Coin Change)
Najmanji broj novčića i broj načina.
Otvori lekciju →Rastojanje uređivanja (Edit Distance)
Najmanji broj izmena između dve reči.
Otvori lekciju →DP na DAG-u
Dinamičko programiranje po topološkom redosledu grafa.
Otvori lekciju →Predloženi redosled
Korisni spoljni resursi
- AtCoder Educational DP Contest – 26 zadataka od najlakšeg do teškog
- CSES Problem Set – odeljak „Dynamic Programming“
- USACO Guide – Introduction to DP
Mapa učenja — Rekurzija i dinamičko programiranje
Ova stranica predstavlja put kroz lekcije o rekurziji i dinamičkom programiranju (DP)
za učenje algoritama i pripremu za takmičenja iz informatike
(SIO, okružno i državno takmičenje).
Preporučujemo da najpre savladaš osnove rekurzije, a zatim pređeš na
dinamičko programiranje i njegove najvažnije obrasce.
Izaberi oblast koja ti je potrebna ili prati predloženi redosled od početka do kraja.
□ 1. Osnove rekurzije
Rekurzija je tehnika u kojoj funkcija poziva samu sebe. Važno je razumeti bazni slučaj, rekurzivni korak i način na koji se problem postepeno svodi na jednostavnije potprobleme.
Cilj: razumeti kako funkcionišu rekurzivni pozivi i zašto je bazni slučaj neophodan da bi se izbeglo beskonačno pozivanje funkcije.
□ 2. Uvod u dinamičko programiranje
Dinamičko programiranje se koristi kada problem može da se razloži na potprobleme koji se ponavljaju. Umesto da iste rezultate računamo više puta, možemo da ih zapamtimo i ponovo upotrebimo.
Važni pojmovi: potproblemi, memoizacija, preklapanje potproblema i računanje rezultata na osnovu prethodno izračunatih vrednosti.
Preporučeni redosled: Uvod u dinamičko programiranje → Fibonaccijev niz, memoizacija i DP.
□ 3. Osnovni DP obrasci
U ovoj grupi nalaze se klasični problemi na kojima se uči kako da se definišu stanja dinamičkog programiranja, početne vrednosti i prelazi između stanja.
- Problem ranca (Knapsack)
- Subset Sum — izbor elemenata sa zadatim zbirom
- LCS — najduža zajednička podsekvenca
Na šta treba obratiti pažnju: šta predstavlja stanje DP-a, kako se do njega dolazi iz prethodnih stanja i kako se izračunati rezultati koriste za dobijanje konačnog rešenja.
□ 4. Napredni DP obrasci i primene
Nakon savladavanja osnovnih obrazaca, pređi na probleme koji zahtevaju pažljiviji izbor stanja, prelaza ili načina predstavljanja potproblema.
- Dinamičko programiranje na mreži (Grid DP)
- Coin Change — problem razmene novca
- Edit Distance — najmanje izmene između stringova
Cilj: naučiti kako se DP primenjuje na različite strukture problema, uključujući putanje kroz mrežu, kombinovanje novčanih apoena i pretvaranje jednog stringa u drugi.
□ 5. Predložen redosled učenja
- Rekurzivni algoritmi
- Uvod u dinamičko programiranje
- Fibonaccijev niz, memoizacija i DP
- Problem ranca (Knapsack)
- Subset Sum
- LCS — najduža zajednička podsekvenca
- Dinamičko programiranje na mreži (Grid DP)
- Coin Change — problem razmene novca
- Edit Distance
Preporuka: nemoj učiti samo gotova rešenja. Za svaki problem pokušaj da sam odrediš stanje DP-a, početne vrednosti, prelaz i redosled računanja. Zatim proveri rešenje na nekoliko malih primera.
□ Kuda dalje?
Kada savladaš ove lekcije, pokušaj da prepoznaš kada se dinamičko programiranje može primeniti na novi problem. Posebno je korisno uporediti rekurzivno rešenje, rešenje sa memoizacijom i iterativno DP rešenje.
⭐ Ova putanja predstavlja osnovu za dalje proučavanje algoritama i pripremu za naprednije zadatke na takmičenjima iz informatike.
