h2. '1expr':problema/1expr

Problema se rezolva folosind programare dinamica. Pentru fiecare $K$ de la 1 la $3^8^$ se calculeaza lungimea minima a unei $1-expresii$ care are ca rezultat pe $K$, iar ultima operatie efectuata in cadrul acestei $1-expresii$ este $+$, $*$, $^$ sau $!$ (deci se calculeaza $4$ valori). Este important sa se calculeze toate aceste $4$ valori si nu doar o singura lungime minima a unei $1-expresii$ care il are ca rezultat pe $K$, deoarece este posibil ca acea $1-expresie$ sa se obtina folosind operatori de prioritate mica si, pentru a fi folosita in cadrul unor expresii mai mari, sa trebuiasca puse intre paranteze.

Problema se rezolva folosind programare dinamica. Pentru fiecare $K$ de la 1 la $3^8^$ se calculeaza lungimea minima a unei $1-expresii$ care are ca rezultat pe $K$, iar ultima operatie efectuata in cadrul acestei $1-expresii$ este $+$, $*$, $^$ sau $!$ (deci se calculeaza $4$ valori). Este important sa se calculeze toate aceste $4$ valori si nu doar o singura lungime minima a unei $1-expresii$ care il are ca rezultat pe $K$, deoarece este posibil ca acea $1-expresie$ sa se obtina folosind operatori de prioritate mica si, pentru a fi folosita in cadrul unor expresii mai mari, sa trebuiasca pusa intre paranteze.

De exemplu, $1-expresia$ de lungimea minima pentru $8$ este: $1+1+(1+1+1)!$. O alta scriere a lui $8$, care are lungimea cu $1$ mai mare este: $(1+1)^(1+1+1)$. Insa aceasta a doua reprezentare a lui $8$ poate fi folosita fara a fi inclusa intre paranteze, daca trebuie inmultita cu o alta expresie, in timp ce prima scriere trebuie inclusa intre paranteze.