ここで説明されている問題を考えてみてください（以下に再現）。よりよく知られているNP完全問題をそれに還元することはできますか？
問題：
家の列があります。各家は、赤、青、緑の3色で塗装できます。それぞれの家を特定の色で塗る費用は異なります。隣接する2つの家が同じ色にならないように、すべての家をペイントする必要があります。あなたは最小の費用で家を塗らなければなりません。どうしますか？
注：ハウス1の赤の塗装のコストは、ハウス2の赤の塗装のコストとは異なります。家と色の組み合わせごとに独自のコストがあります。
いいえ、それはNP困難ではありません（技術的には、これは決定問題ではないため、「NP完全」はこれに対して間違った用語です）。
動的計画法は機能し、O（n）時間アルゴリズムを提供します。（nは家の数です）。
あなたは3つの配列R[1..n], B[1..n], G[1..n]を維持します。ここで、は赤に着色されたR[i]家1、2、3...を塗装するための最小コストですi。i同様にB[i]、1、2 ...iをi青に着色G[i]し、i緑に着色する場合の最小コストです。
あなたは計算することができますR[i+1]：
R[i+1]= (Cost of painting house i+1 Red) + minimum {G[i], B[i]}。
同様にB[i+1]、G[i+1]計算することができます。
最終的には、の最小値を取りますR[n], B[n] and G[n]。
これはO（n）時間とO（n）空間です。
たとえば、住宅の次のコストマトリックスについて考えてみます。
ハウス番号：1 2 3 R：1 4 6 G：2 100 2 B：3 100 4
アルゴリズムは、答えを得るために次のマトリックスを構築しています。
住宅：0 1 2 3 R：0 1 6107 G：0 2 101 8 B：0 3 101 10
3つの家すべてが塗装されている最後の列から、最小コストを見つけることができます。これは8に等しく、[緑（2）、赤（4）、緑（2）]の組み合わせに対応します。
クイックPython：
# rc = costs of painting red, bc of blue and gc of green.
def min_paint(rc, bc, gc):
n, i = len(rc), 1
r, b, g = [0]*n, [0]*n, [0]*n
r[0], b[0], g[0] = rc[0], bc[0], gc[0]
while i < n:
r[i] = rc[i] + min(b[i-1], g[i-1])
b[i] = bc[i] + min(r[i-1], g[i-1])
g[i] = gc[i] + min(b[i-1], r[i-1])
i += 1
return min(r, b, g)
def main():
print min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])
if __name__ == "__main__":
main()
出力は（[1、6、107]、[2、101、8]、[3、101、10]）になります。これは、ソリューションにつながるコストマトリックスです。
@Knootheによる説明は的確ですが、実装を改善できると思いO(n)ます。以前の値を格納するために追加のスペースを使用しO(1)ますが、各色の以前の値のみが必要であり、値の配列全体。方法は次のとおりです。
def min_paint(rc, bc, gc):
# `r` is the min cost of painting the current house
# using color red; similarly for `b` and `g`
r, b, g = 0, 0, 0
for cr, cb, cg in zip(rc, bc, gc):
# new value for `r` is current cost for `r` plus the
# minimum cost for painting the previous house in one
# of the other two colors; similarly for `b` and `g`
r, b, g = cr + min(b, g), cb + min(r, g), cg + min(r, b)
# answer is the min cost for painting the last house
return min(r, b, g)
例えば：
min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])
=> 8