Cum de a crea un algoritm pentru rezolvarea problemei în AM sau recursivitate (problema pe scara)

  • programare
  • matematică
  • C ++
  • algoritmi
  • Olympiad programare

Cum de a crea un algoritm pentru rezolvarea problemei în AM sau recursivitate (problema pe scara)

Am citit că aceste probleme sunt rezolvate prin așa-numita „programare dinamică“, dar, din păcate, deși am înțeles esența acestei metode, soluții de calificare ollimpiadnyh de probleme nu este de ajuns.

De asemenea, se poate vedea că această problemă poate fi rezolvată printr-o căutare recursiv, dar, de asemenea, nu a reușit să facă algoritmul de decizie corectă.

Aș dori să obțină sfaturi cu privire la ce cărți sau articole de citit pentru a înțelege astfel de probleme.
Precum și sugestii cu privire la modul de a rezolva problema unui subiect.

încercările mele au eșuat.
Cel mai bun este ceea ce am venit la teorie, această similitudine algoritm recursiv: habrastorage.org/files/82b/160/5cc/82b1605cc82b414.
(Fiecare scara scade de la capătul de la 1 mor, și este considerat „rupt“ parte)

Undeva am dat peste o soluție incredibil de frumos în Java, a rescris-o în C ++, dar pentru mine este absolut magie, poate că cineva va explica ce se întâmplă, și pe ce bază se sprijină toate: pastebin.com/6ACsC9ta

Pentru a rezolva problema ușor - manivelă matrice A [N, N], în fiecare celulă de [K, M], care este scris numărul de scări ale blocurilor K, stratul inferior al cărui format din blocuri M. Numărul va fi non-zero, atunci când M <= K <= M*(M+1)/2.
Matricea este umplut cu cusatura de pornire K = 1 formula A [K, M] = suma (A [K-M, r], r = 1..M-1). Cantitatea de elemente în rândul K = N este numărul dorit.

În decizia, link-ul la care ați dat calculat în mod constant numărul de trepte din cuburi j, rândul de jos, care nu este mai mare de i blocuri. Pentru a găsi acest număr, este necesar să se fi găsit pe scări, rândul de jos nu sunt mai mult decât i-1 cub (care vom lăsa neschimbat), se adaugă cuburi ji scări cu nu mai rândul de jos decât i-1 cub (pentru a le-am i se va adăuga un număr de zaruri). Ceea ce se face în bucla interioară.

Încerc să înțeleagă și să codul decizia ta, dar nu înțeleg.
întrebări:
1) Cum se ajunge la această decizie? (Ce să citești?)
2) Din această condiție: M <= K <= M*(M+1)/2
3) În acest caz, A [K, M] = suma (A [K-M, r], r = 1..M-1), așa cum va fi M?
4) Un Array indexat de la 0 sau 1?

În general, aveți nevoie de o analiză mai detaliată.