Con l’arrivo del nuovo esercizio mle apro le discussioni relative a questo esercizio.
Provo a dare un’idea del metodo risolutivo di questo esercizio. Come è facile notare si tratta di game theory e la programmazione dinamica è essenziale per risolverle il problema. Definendo dp(i) come lo score massimo che si può ottenere con le ultime i monete si nota facilmente come, per calcolare dp(i) tornano comodi dp(i-1), dp(i-2), .., dp(i-k). Infatti con i monete rimaste dp(i-1), dp(i-2), .., dp(i-k) rappresentano gli score che il mio avversario può effettuare dopo la mossa corrente. L’obiettivo è quindi prendere x monete in modo che l’avversario ottenga meno punti possibili sapendo che il mio score con i monete rimaste è uguale alla somma delle prime i monete meno lo score avversario, quindi dp(i)=sum[i]-min(dp[i-1]..dp[i-K]).
In base all’algoritmo e alla struttura dati utilizzati si ottengono complessità computazionali differenti, la soluzione richiesta ha complessità O(N) , al momento evito di dare specifiche tecniche sull’algoritmo richiesto in quanto considero più utile l’idea proposta precedentemente, ma ovviamente siamo aperti a discussioni di ogni genere.