Ciao.
Ho un dubbio su come risolvere questo esercizio: ktree (https://cms.di.unipi.it/#/task/kfree/statement) però il problema è valido anche per un altro esercizio che non ricordo.
Ho un caso esempio l’array di soluzioni è
[0] [1] [2] [3]
1 2 3 3 Array di soluzioni
- 0 1 1 Array di soluzione precedente
Che significa ad esempio la soluzione[3] è calcolata a partire dalla soluzione[1] che a sua volta dalla soluzione[0]
cioè [0] <-- [1] <-- [3]
Il problema si pone ad esempio che l’elemento 3 è “incompatibile” con l’elemento 0 ma ok con l’elemento 1
cioè la relazione [1] <-- [3] è ok, ma [0] <-- [3] no.
Il problema sorge quando devo verificare che posso calcolare sol[3] a partire da sol[1], non so come verificare che sol[1] deriva da sol[0] e quindi non posso calcolare sol[3] a partire da sol[1].
Non so come implementare l’algoritmo. La idea principale di salvare la provenienza della soluzione e a ritroso controllare se è presente una soluzione proibita che tuttavia potrebbe dare origine a problemi
Sono stato chiaro o confusionario?
Riusciresti a spiegare meglio come intendi utilizzare la programmazione dinamica per risolvere questo problema?
Temo non sia l’approccio giusto in questo caso 
Il ragionamento è cosi. Se gli elementi se
Ripeti i da 0 a N-1
Max = 0
Ripeti j da 0 a i-1
Se Ele[j]*K == Ele[i]
Salta giro
Altrimenti
Se Max < Sol[j] ==> Max = Sol[j]
Sol[i] = Max + 1
Non sono ancora sicurissimo di aver capito, magari prova a spiegarlo a parole comunque non mi pare che si tratti di programmazione dinamica…
Però posso darti questo consiglio, utilizza un array grande quanto il numero più grande che compare nella sequenza : ciascun elemento sarà true o false in base alla presenza del suo indice nella sequenza.
In questo modo con un semplice ciclo su questo array, puoi sapere per ciascun numero se deve o meno essere rimosso 
EDIT: Credo di non essere stato molto chiaro, inoltre non avendo ancora capito se la tua soluzione possa funzionare non vorrei proportene un’altra ignorando la tua. Comunque per chiarirmi meglio ti lascio un esempio [spoiler]
K = 2
Sequenza: 4 3 2 9 6
Array di bool di dimensione 9
valore: F T T T F T F F T
indice: 1 2 3 4 5 6 7 8 9
Con un semplice ciclo, ti puoi accorgere che solo 4 e 6 vadano effettivamente rimossi
[/spoiler]
Nel caso d’esempio il tuo codice farebbe:
sol[0]=1;
sol[1]=sol[0]+1=2;
sol[2]=1;
sol[3]=sol[1]+1=3;
e fino a qua andrebbe anche bene, solo che quando arriva a sol[4], prende sol[3] come massimo dato che 4*2 non fa 5 e quindi sol[4]=sol[3]+1=4
peccato che sol[3] prende anche gli elementi 2 e 3 e in questo caso 2 non può stare con 4.
Nei tag c’è scritto programmazione dinamica ma a mio parere non si risolve così 
4 Mi Piace
Ho pensato anch’io qualcosa del genere, però dovrei implementare 100000*100000 Bytes = 1,192 GB
Oppure ricorsivamente, oppure alla dijskra
Ho pensato anch’io qualcosa del genere, però dovrei implementare 100000*100000 Bytes = 1,192 GB
In realtà no, ti servono solamente 10^5 bool, anche dichiarando un array di bool non superi i 100KB
