Ajutor cu tehnica de programare dinamica

[•Viva12]

Salut ! 
Sunt elev în clasa XII-a la un liceu din Brașov. Data fiind pasiunea mea pentru informatică, am încercat sa particip la olimpiade și concursuri de info, însa fără a avea prea mare succes. Dacă cu grafurile/stringurile/geometria ma mai descurc cât de cât, am o mare problema cu programarea dinamica.

Am tot încercat sa caut surse de unde as putea să învăț însa se pare ca am o problema cu înțelegerea ei. Nu îmi dau seama cum pot găsi dinamica pe anumite probleme. Am probleme chiar și cu unele clasice. Mi-am dat seama că probabil îmi lipsesc niște baze teoretice sau un anumit mod de gândire și astfel vroiam sa vă rog, dacă poate cineva, să mă îndrume spre nişte site-uri, cărţi sau chiar să îmi povestească pe scurt cum reuşeşte să deducă dinamicile.

Cam care ar fi pașii de abordare ai unei probleme de programare dinamica ? 

Mersi fain !

[•PlayLikeNeverB4]

Gasesti starea, apoi relatia de recurenta si te asiguri ca tranzitiile sunt aciclice.

Programarea dinamica o inveti rezolvand probleme si apoi o sa vezi ca o sa incepi sa te prinzi.

[•laurion]

E mai usor sa incepi cu metoda top-bottom (memoizare). Vezi sfaturile mele de aici:

http://www.quora.com/Algorithms/I-want-to-learn-memoization-Can-you-give-me-some-links-with-problems-from-spoj-topcoder-codeforces

Fiind timpul atat de scurt, cel mai bine e sa faci, pe rand, probleme de aici: http://community.topcoder.com/tc?module=ProblemArchive&sc=7&sd=desc&maxd2s=&div2l=&cat=Dynamic+Programming&div1l=&class=&wr=&mind2s=&mind1s=&maxd1s=

Sunt ordonate in ordine crescatoare a dificultatii. Rezolva-le in practice room! (applet-ul topcoder il descarci din stanga sus unde e semnul "O(N)")

[•Viva12]

Va mulțumesc mult tuturor !

Si scopul meu nu este OJI-ul de sâmbăta. Sunt conștient ca nu am șanse la dinamici într-un timp atât de scurt. As vrea însa sa ma pun și eu la punct cu metoda asta ca îmi da mari bătăi de cap. Si având în vedere ca vreau sa urmez o cariera în domeniu, bănuiesc ca este un pas înainte. Știu ca se pune accentul mai putin pe algoritmica pura, însa dinamica e o ambiție de a mea pe care sper sa o lămuresc în cele din urma.