Z-Draguljcici Z-Orasi

Interesuje me princip resavanja ovih(i slicnih) problema,ako moze sto detaljnije.Jednostavno,nemam nikakvu ideju...

z-orasi:
Pa, u ovom problemu moras neko primeniti stepenovanje matrice..
Prvo uradi z-funkciju (postoji thread) pa posle razmishljaj o z-orasima..

z-draguljcici:
posto su ogranicenja relativno mala, moglo bi da se radi dinamicki..
Ako nisi upoznat sa DP-om procitaj neki tutorial..

Hmmm,znaci ovo nisu dva slicna problema?dobro...Znam DP,ali ne uocavam odakle da krenem,suvise si mi generalno odgovorio.A za prvi problem uopste ne umem da postavim pocetnu matricu....

pa z-draguljcici bi trebali biti tipican primer DPa..

int res = 0;
dp[0] = 1;
for(int i = 0; i <= m; i++) {
  res += dp[i];
  for(int j = 0; j < n; ++j)
       dp[i + v[j]] += dp[i];
}

uvek mi je lakse odgovoriti koodom kada je dp u pitanju :)..

Inace, ovo veoma slicni problemi..s tim sto nisam siguran
da bi z-draguljcici mogli da se optimizuju kao z-orasi..
A z-orahe slobodno preskoci..odradi neke DP probleme..
vise ce ti koristiti nego on..pa se mozda kasnije vratis..

Hvala.U mojoj glavi je to bio mnogo komplikovaniji problem :)

Zasto dp[0]=1? ???

Zato sto duzinu 0 mozes preci samo na jedan nacin (tacnije, to je pocetak i samo sa te pozicije polazis).