ダイナミックプログラミング - ペイントフェンスアルゴリズム

Question

nのポストがあり、各ポストはkのいずれかの色で塗りつぶすことができます。あなたは、2つ以上の隣接するフェンスポストが同じ色を持たないように、すべてのポストをペイントする必要があります。フェンスをペイントする方法の総数を返します。

差分 - 異なる色の組み合わせの数、
同じ - 同じ色の組み合わせの数、
N - 投稿の数、
K - 色の数。

についてN = 1：

diff = k; 
same = 0; 

についてN = 2：

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

N = 3の場合：

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

、最終式は、

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

same[i]の検索方法はわかりましたが、diff[i]の検索方法はわかりません。 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

ここにcombinatorics引数があります。

diff[i, c]を、最後のフェンスが色cで塗りつぶされるような問題文の規則に従ってiの投稿をペイントする方法の数にします。

は、我々は持っている：各cに対して

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

は、我々がiを描く、（我々は前々回が何であるかを気にしない、その場合には）c' != cで終了するか、以前の、または前の二c'' != cで終わることがあります（その場合は、前の内容は気にしません）。

とk - 1の可能性はc'' != cです。だから我々は再発からcをドロップすることができますし、単に書く：

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

あなたが持っているものはどれ。