h1(#propozitie). 'Propozitie':problema/propozitie

Fie $S$ sirul initial de caractere. Vom rezolva problema cu ajutorul programarii dinamice. Vom construi o matrice $A$, in care $A[i][j]$ va reprezenta numarul de posibilitati de a obtine propozitii valide cu primele $i$ caractere, iar ultimul cuvant din propozitie sa aibe exact $j$ vocale. Pentru a calcula valorile $A[i][j]$ putem proceda in urmatorul fel: alegem intai subsecventa de litere $S{~j~}S{~j+1~}...S{~i~}$ si o vom considera pe aceasta ultimul cuvant dintr-o propozitie valida. Daca subsecventa de litere de la $k$ la $i$ contine $p$ vocale atunci va trebui sa adunam la $A[i][p]$ toate valorile $A[j-1][q]$, unde $q$ este cuprins intre $0$ si $K$. Evident vom considera doar subsecventele pentru care $p ≤ K$. O implementare bruta a acestei solutii va avea complexitatea $O(N*N*K)$. Putem reduce complexitatea la $O(N*N)$ daca vom precalcula $B[i] = A[i]{@[0]@} + A[i][1] + ... + A[i][K]$. Plecand de la aceasta idee putem dezvolta o solutie de complexitate $O(N*K)$. Vom calcula $A[i][j][0]$ numarul de propozitii valide formate cu primele $i$ caractere in care ultimul cuvant are $j$ vocale si se termina pe pozitia $i$ si $A[i][j][1]$ numarul de propozitii valide cu primele $i$ caractere in care ultimul cuvant are $j$ vocale si nu se termina pe pozitia $i$. Relatiile de recurenta se obtin usor in $O(1)$ si complexitatea va fi $O(N*K)$ ca timp si $O(K)$ ca memorie (observam ca sunt suficiente doar ultimele doua linii din matrice). Putem optimiza si mai mult aceasta solutie observand ca de fapt daca am calcula $B[i]$ fiind numarul de propozitii valide continand doar primele $i$ caractere, $B[i] = B[i-1]+B[i-2]+...+B[j]$, unde $j$ este cel mai mic posibil astfel incat $S{~j+1~}S{~j+2~}..S{~i~}$ are cel mult $K$ vocale. Cand suntem la pasul $i$ vom avea un indice $j$, la trecerea la pasul $i+1$ se observa ca acest indice ori ramane la fel, ori in cazul in care $S{~i+1~}$ este vocala si aveam deja $K$ vocale indicele $j$ creste pana cand vom avea din nou cel mult $K$ vocale. Astfel putem obtine o solutie in complexitate $O(N)$ ca timp si de asemenea $O(N)$ ca memorie. Oricare din aceste ultime doua solutii obtinea punctajul maxim.

Fie $S$ sirul initial de caractere. Vom rezolva problema cu ajutorul programarii dinamice. Vom construi o matrice $A$, in care $A[i][j]$ va reprezenta numarul de posibilitati de a obtine propozitii valide cu primele $i$ caractere, iar ultimul cuvant din propozitie sa aibe exact $j$ vocale. Pentru a calcula valorile $A[i][j]$ putem proceda in urmatorul fel: alegem intai subsecventa de litere $S{~j~}S{~j+1~}...S{~i~}$ si o vom considera pe aceasta ultimul cuvant dintr-o propozitie valida. Daca subsecventa de litere de la $k$ la $i$ contine $p$ vocale atunci va trebui sa adunam la $A[i][p]$ toate valorile $A[j-1][q]$, unde $q$ este cuprins intre $0$ si $K$. Evident vom considera doar subsecventele pentru care $p ≤ K$. O implementare bruta a acestei solutii va avea complexitatea $O(N*N*K)$. Putem reduce complexitatea la $O(N*N)$ daca vom precalcula $B[i] = A[i]{@ [0] @} + A[i]{@ [1] @} + ... + A[i]{@ [K] @}$. Plecand de la aceasta idee putem dezvolta o solutie de complexitate $O(N*K)$. Vom calcula $A[i][j]{@ [0] @}$ numarul de propozitii valide formate cu primele $i$ caractere in care ultimul cuvant are $j$ vocale si se termina pe pozitia $i$ si $A[i][j]{@ [1] @}$ numarul de propozitii valide cu primele $i$ caractere in care ultimul cuvant are $j$ vocale si nu se termina pe pozitia $i$. Relatiile de recurenta se obtin usor in $O(1)$ si complexitatea va fi $O(N*K)$ ca timp si $O(K)$ ca memorie (observam ca sunt suficiente doar ultimele doua linii din matrice). Putem optimiza si mai mult aceasta solutie observand ca de fapt daca am calcula $B[i]$ fiind numarul de propozitii valide continand doar primele $i$ caractere, $B[i] = B[i-1]+B[i-2]+...+B[j]$, unde $j$ este cel mai mic posibil astfel incat $S{~j+1~}S{~j+2~}..S{~i~}$ are cel mult $K$ vocale. Cand suntem la pasul $i$ vom avea un indice $j$, la trecerea la pasul $i+1$ se observa ca acest indice ori ramane la fel, ori in cazul in care $S{~i+1~}$ este vocala si aveam deja $K$ vocale indicele $j$ creste pana cand vom avea din nou cel mult $K$ vocale. Astfel putem obtine o solutie in complexitate $O(N)$ ca timp si de asemenea $O(N)$ ca memorie. Oricare din aceste ultime doua solutii obtinea punctajul maxim.