Peisaj
Răspunsul la subpunctul a) este echivalent cu numărul parantezărilor corecte şi se poate calcula cu formula numerelor Catalan. Totuşi, putem observa, că subpunctul a) este de fapt un caz special al subpunctului b), când K = 1.
Pentru a rezolva subpunctul b) vom aplica metoda programării dinamice. O stare va fi definită prin trei parametri:
- Bi,j,b (i = 1, 2, ..., N; j = 0, 1, ..., N/2, b = {adevărat, fals}) – numărul de posibilităţi prin care după aşezarea a i beţişoare se poate ajunge la nivelul j, astfel încât cerinţa problemei (de a ajunge cel puţin odată la nivelul K) să fie sau nu satisfăcută.
Recurenţele vor fi:
- Bi,j, fals = Bi-1,j-1,fals + Bi-1,j+1,fals
- Bi,j,adevărat = Bi-1,j-1,adevărat + Bi-1,j+1,adevărat, dacă j != K
- Bi,j,adevărat = Bi-1,j-1,fals + Bi-1,j+1,adevărat, dacă j = K
Subpunctul c) se rezolvă tot cu metoda programării dinamice. Aici vom defini o stare în modul următor:
- Ci,j,v,u (i = 1, 2, …, N, j = 0, 1, N/2, v = 0, 1, …, K, u = {/, \} – numărul posibilităţilor prin care după aşezarea a i beţişoare se poate ajunge la nivelul j, formând v vârfuri în aşa fel încât ultimul beţişor aşezat să fie de forma u.
Recurenţele vor fi:
- Ci,j,v,/ = Ci-1,j-1,v,/ + Ci-1,j-1,v,\
- Ci,j,v,\ = Ci-1,j+1,v,\ + Ci-1,j+1,v-1,/
Răspunsurile finale se vor afla în Bn,0,0, Bn,0,1, respectiv Cn,0,k,\. Complexitate finală: Θ(N2 * K).
