419 Desc2

[•DITzoneC]

Aici puteţi discuta despre problema Desc2.

[•sima_cotizo]

Am incercat sa fac problema asta cu mapuri stl; avand in vedere solutia oficiala am facut o functie recursiva si am vrut sa memoizez... Problema e ca iau 3 TLE, am cum sa imbunatatesc cu alta structura sau incerc sa gasesc o metoda mai buna la implementarea functiei?

[•astronomy]

Poti face o dinamica cu O(N) memorie.

[•Marius]

Eu am O(N*K) memorie, insa am alocat dinamic pentru K.

[•Florian]

Poti face o dinamica cu O(N) memorie.

Ai vrea sa explici putin ideea? Multumesc!

[•dicu_daria]

In solutia oficiala apare o recurenta pentru a calcula numarul de posibilitati de a scrie un numar N ca suma de k numere naturale pozitive, chiar si egale:
S(N,k)=S(N-k,1)+S(N-k,2)+...+S(N-k,k) si se spune ca e formula Stirling. Eu totusi nu inteleg legatura cu numerele lui Stirling pentru ca stiam recurenta ca fiind altfel. Am incercat sa caut si pe net, dar nu gasesc decat recurentele de la numerele lui Stirling care apar si in articolul din Arhiva Educationala.
Ar putea cineva sa imi explice sau sa imi trimita un link unde e explicata recurenta asta?