h3. problema grea, clasele 11-12
Vom calcula $P[i, j]$ = numarul de permutari ale multimii {{$1$},{$2$},..,{$i$}} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N, 1]$ + $P[N, 2]$ + ... + $P[N, N]$.
Prima solutie corecta este de complexitate O(N*2^N^). Se calculeaza o matrice $P[i, R]$ = numarul de permutari cu $i$ elemente, care respecta relatia $R$ ($R$ este un numar binar de $i - 1$ biti, care codifica un sir de relatii). Putem calcula aceste valori pe baza valorilor calculate pentru $P[i - 1, R']$, variind pozitia in care este asezat in cadrul permutarii cel de-al $i$-lea element. Aceasta solutie nu se incadreaza, insa, nici in limita de timp, nici in cea de memorie.
Ideea solutiei de punctaj maxim este urmatoarea: Vom calcula $P[i, j]$ = numarul de permutari ale multimii {{$1$},{$2$},..,{$i$}} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N, 1]$ + $P[N, 2]$ + ... + $P[N, N]$.
Pentru calculul lui $P[i, j]$ vom observa ca, eliminand numarul $j$ din permutare, obtinem $i-1$ numere distincte care pot fi renumerotate pentru a forma o permutare a multimii {{$1$},{$2$},..,{$i-1$}}. Mai exact, orice numar $x$ mai mare decat $j$ este renumerotat cu valoarea $x-1$. In conditiile acestei renumerotari, avem urmatoarele $2$ cazuri:
* daca relatia $i-1$ este "$<$", atunci $P[i, j]$ = $P[i-1, 1]$ + $P[i-1, 2]$ + ... + $P[i-1, j-1]$
