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
Kako prepoznati DP: zadatak traži najbolju vrednost ili broj načina, a rešenje za veći ulaz može da se sastavi od rešenja za manje ulaze. Prvo definiši stanje (šta pamtiš), pa prelaz (kako se računa iz manjih stanja).

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.

Predloženi redosled

  1. Uvod u dinamičko programiranje
  2. Fibonači, memoizacija i DP
  3. Knapsack
  4. Subset Sum
  5. LCS
  6. Grid DP
  7. Coin Change
  8. Edit Distance

Korisni spoljni resursi