Ho un problema con un compito. In questo incarico devo creare un programma che deve calcolare quante diverse possibilità ci sono per ottenere dal numero a al b. Per ottenere da a a b puoi solo D (doppio) il valore o I (incrementare) il valore.
Quindi puoi avere a = 3 eb = 14. Questo ti porterà 8 diverse possibilità:
DDII = 3*2*2+2 = 14
DID = ((3*2)+1)*2 =14
DIIIIIIII = 3*2+8 =14
IDIIIIII=(3+1)*2+6=14
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=14
IIIIIIIIIII=3+11=14
Nella mia attuale soluzione sto usando una ricerca per ampiezza (BFS) per calcolare tutte le possibilità solo questo è molto lento, perché a volte ci sono molte possibilità e con BFS passerai attraverso tutte loro. Quindi, per esempio, se vuoi calcolare a = 10 eb = 1000, questo mi darà 74.116.423 possibilità.
Questo è quasi impossibile da calcolare con il mio computer e la soluzione che sto attualmente utilizzando.
Qual è l'approccio corretto da adottare per risolvere questo problema? Essendo un incarico, non cerco la risposta, ho bisogno di un algoritmo o di altra spinta nella giusta direzione.