Grigo
O analiza atenta a structurii permutarilor care respecta conditiile impuse ne arata ca daca ultima pozitie trebuie sa fie vizibila atunci in toate permutarile pe acea pozitie se va afla valoarea N, iar in caz contrar pe ultima pozitie se poate afla orice valoare intre 1 si N-1. De aici vine ideea construirii unei solutii bazate pe programare dinamica. Vom calcula un vector NrSol[i], reprezentand numarul de permutari de i numere ca respecta conditiile impuse daca se iau in considerare doar pozitiile de la 1 la i. Recurenta este destul de simplu de dedus. Astfel, daca pozitia i trebuie sa fie vizibila, atunci in mod evident NrSol[i] = NrSol[i-1], deoarece pe pozitia i este necesar sa se afle valoarea i. Daca pozitia i nu trebuie sa fie vizibila, atunci NrSol[i] = (i-1) * NrSol[i-1], deoarece pe ultima pozitie putem pune orice numar intre 1 si i-1, ramanandu-ne astfel i-1 valori distincte, pe care le putem reinterpreta ca fiind o permutare. Raspunsul cautat se va gasi in NrSol[N].
