Dynamische Programmierung - Farbe Zaun Algorithmus

Question

Es gibt einen Zaun mit n Beiträge, jeder Beitrag kann mit einer der k Farben gemalt werden. Sie müssen alle Pfosten so malen, dass nicht mehr als zwei benachbarte Zaunpfosten die gleiche Farbe haben. Gibt die Gesamtzahl der Möglichkeiten zurück, mit denen Sie den Zaun malen können.

diff - Anzahl von Kombinationen mit verschiedenen Farben,
gleiche - Anzahl von Kombinationen mit gleichen Farben,
n - Anzahl der Beiträge,
k - Anzahl der Farben.

Für n = 1:

diff = k; 
same = 0; 

Für n = 2:

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

Für n = 3:

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

und die endgültige Formel:

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

Ich verstehe, wie man same[i] findet, aber ich verstehe nicht, wie man diff[i] findet. Können Sie die Formel für diff[i] erklären?

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

Hier ist ein kombinatorisches Argument.

Lassen Sie diff[i, c] die Anzahl der Möglichkeiten sein, i Beiträge nach den Regeln der Problemstellung zu malen, so dass der letzte Zaun mit Farbe c lackiert wird.

Wir haben:

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

Für jede c wir i malen mit der vorherigen entweder mit einem c' != c enden kann (in diesem Fall werden wir interessiert nicht, was die zweite vorherigen ist) oder der zweite vorherige kann mit einer c'' != c enden (in diesem Fall ist uns egal, was der vorherige ist), oder beides.

Es gibt k - 1 Möglichkeiten für c' != c und k - 1 für c'' != c. So können wir c aus der Wiederholung fallen und einfach schreiben:

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

Welche ist das, was Sie haben.