家を着色するための最低コストは？

Question

問題が発生しました

N個の家が連続しています。各家は赤、 緑または青のいずれかで塗装することができます。 の各色の各家に色を付けるコストは異なります。各家の色を見つけて、隣接する家が同じ色を持っていないようにしてください。 すべての家が最小です。ここで

目的は、コストをminmizeとは、隣接する家が同じ色を持っていないことを確認することですと私には問題が、少し混乱に見えるcomplete question

です。その場合、私は を選択するべきではありません。

は色

1. のコストであるレッド$ 100
2. 私はここで

   をペイントする5行家を持っているブルー$ 300

がなるグリーン$ 200

ここで言います私のアルゴ

そのコストとして

1. 選択赤と緑の色が5％2

2. 計算最小です。

   5％2 == 1の場合、最後から最後の家の色を赤（$ 100）として選択します。さて、代替色に私はIs "house coloring with three colors" NP?は、動的計画法を提案参照

を最初から開始し、選択し

% 2 == 0 5場合は、代替色を選択してくださいしかし、私は私のアプローチが間違っているかわからないですここで動的プログラミングが必要な理由

Answer 1

これは（おそらく）宿題の問題です。

1. 最も安い色（「赤」）を使用して最初の家をペイントします。
2. 最も安い色を使用して次の家をペイントします。

「赤」と「緑」の間で2番目の色が交互に表示されますが、あらかじめ色を選択する必要はありません。

この問題を割り当てていた場合、次の問題は「1つの赤い家のために十分な塗料しかないと仮定すると、これを解決します。