Ovviamente, al crescere di n e k non possiamo assolutamente rilanciare ogni volta le chiamate a tutti i sottoproblemi ma dobbiamo farci una tabella dei problemi risolti.
La prima cosa che viene in mente e' quindi una programmazione dinamica.
Se provate ad implementare una soluzione, scoprirete che il problema da pero' dei colpi di coda, in quanto FS(n,k) esplode al crescere di n.
In particolare, e' difficile che FS(64, k) vi stia in un long int per k = 3, e tuttavitesto dell'esercizio prospetta istanze con n assai superiore a 64.
Un attimo di riflessione porta a concludere che questa apparente contraddizione si risolve col fatto che in verita' FS(n,k) cala (e drasticamente) al crescere di k.
Chiaramente, facendo riferimento alla ricorrenza espressa in hint2.txt,
il vero valore di FS(n,k) sara' del tutto dimentico di quei valori FS(n-i,k-1) tali che FS(n-i,k-1) > FS(n,k).
La gestione di tutto questo introduce delle problematiche.
Il modo piu' conveniente per gestirle e' tagliare la testa al toro e riconoscere in fase di calcolo quelle coppie (n,k) sulle quali si e' avuto overflow e taggarle come tali.