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_jS_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+1S_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.