Problema se rezolva folosind programarea dinamica. Mai intai calculam o matrice $V$, unde $V[i, j]$ reprezinta numarul de sfarsituri valabile de expresii ce se pot forma ce necesita adaugarea a $j$ variabile la inceput pentru a se forma o expresie corecta de lungime $i$. Relatiile de recurenta se determina usor urmarind cu atentie in ce configuratii putem ajunge din configuratia actuala (putem pune o variabila, $+$, $*$ sau $!$).
Rezolvarea celei de-a 2-a parti a problemei implica folosirea matricei $V$. Avand valorile calculate putem afla caracterul pe care trebuie sa il punem pe o anumita pozitie. Este evident ca la fiecare pas indicele expresiei cautate scade cu numarul de expresii peste care "sarim".

O alta solutie este determinarea expresiei cu numarul $P$ caracter cu caracter folosind o functie care determina cate expresii de o lungime fixata exista care incep cu un prefix dat (prefixul fiind un sir de caractere). Pentru a implementa eficient acesta functie se memoizeaza rezultatele intermediare folosind o tabela hash. Prezentam o scurta descriere a acestei proceduri in pesudocod:
 
==code(cpp) |
intreg numara(lungime, prefix)
   daca numara(lungime, prefix) a mai fost apelat returneaza rezultatul stocat in hash;
   daca lungime = 1 si prefix = "" returneaza K;
   daca lungime = 1 si prefix = "A" sau "B" ... sau "Z" returneaza 1;
   daca lungime = 1 returneaza 0;
 
   rez = 0;
   daca |prefix| < lungime sau (|prefix| = lungime si prefix se termina cu "!")
      rez += numara(lungime-1, prefix[1..lungime-1]);
 
   daca |prefix| < lungime sau (|prefix| = lungime si prefix se termina cu "*")
      pentru i = 1, n-2 executa
         rez += numara(i, prefix[1..i])*numara(n-i-1, prefix[i+1..n-i-1]);
 
   daca |prefix| < lungime sau (|prefix| = lungime si prefix se termina cu "+")
      pentru i = 1, n-2 executa
         rez += numara(i, prefix[1..i])*numara(n-i-1, prefix[i+1..n-i-1]);
 
   pastreaza valoarea rez in hash pentru numara(lungime, prefix);
   returneaza rez;
sfarsit functie
|
 

h2. 'Ograzi':problema/ograzi
h3. (problema usoara, clasele 11-12)

h3. (problema grea, clasele 11-12)

Problema se rezolva folosind metoda programarii dinamice, dar
 

==Include(page="template/preoni-2007/footer")==