Programmazione dinamica - algoritmo di recinzione vernice

Question

C'è una recinzione con n post, ogni post può essere dipinto con uno dei colori k. Devi dipingere tutti i post in modo tale che non più di due travi di recinzione adiacenti abbiano lo stesso colore. Restituisci il numero totale di modi in cui puoi dipingere la recinzione.

diff - numero di combinazioni con colori diversi,
stesso - numero di combinazioni con gli stessi colori,
n - numero di posti,
k - numero di colori.

Per n = 1:

diff = k; 
same = 0; 

Per n = 2:

diff = k * (k - 1); 
same = k; 

Per n = 3:

diff = (k + k * (k - 1)) * (k - 1); 
same = k * (k - 1); 

E la formula finale è:

same[i] = diff[i - 1]; 
diff[i] = (diff[i - 1] + diff[i - 2]) * (k - 1); 

Capisco come trovare same[i], ma non capisco come trovare diff[i]. Puoi spiegare la formula per diff[i]?

Answer 1

total[i] = diff[i] + same[i] (definition) 

diff[i] = (k - 1) * total[i-1] 
     = (k - 1) * (diff[i-1] + same[i-1]) 
     = (k - 1) * (diff[i-1] + diff[i-2]) 

Answer 2

Ecco un argomento combinatorio.

Lascia che sia diff[i, c] il numero di modi per dipingere i post i secondo le regole dell'affermazione del problema in modo che l'ultimo recinto sia dipinto con il colore c.

abbiamo:

diff[i, c] = diff[i - 1, c'] + diff[i - 2, c''], c' != c OR c'' != c 

Per ogni c dipingiamo i con il precedente può o terminare con un c' != c (nel qual caso non ci importa quello che il secondo precedente è), o il secondo precedente può terminare con un c'' != c (nel qual caso non ci interessa quale sia il precedente), o entrambi.

Ci sono k - 1 possibilità per c' != c e k - 1 per c'' != c. Così possiamo cadere c dalla recidiva e semplicemente scrivere:

diff[i] = (k - 1) * (diff[i - 1] + diff[i - 2]) 

Che è quello che hai.