给房子上色的最低费用是多少？

Question

我遇到了下面的问题

一排有N栋房子。每栋房子都可以漆成红色、绿色或蓝色。每种颜色给每间房子上色的成本是不同的。找到每栋房子的颜色，这样相邻的两栋房子就不会有相同的颜色，所有房子的着色总成本最低。

这是完整的问题

在我看来，这个问题有点令人困惑，因为目标是将成本降到最低，并确保相邻的房子没有相同的颜色。在这种情况下，我不应该从三种颜色中选择成本最低的两种颜色吗。

这里是颜色的成本

1. 红色100美元

我有5排房子要粉刷

这是我的算法

>

如果5%2==1，则从最后开始，选择最后一栋房子的颜色为红色（$100）。现在选择另一种颜色

如果5%2==0，则从头开始并选择替代颜色

我明白了“三色房屋着色”是NP吗？建议使用动态规划，但我不确定我的方法有什么问题，为什么这里需要动态规划？

Answer 1

这（大概）是个家庭作业问题。我认为目的是教你实现贪婪算法：

1. 用最便宜的颜色（“红色”）粉刷第一栋房子
2. 用最便宜的颜色粉刷下一栋房子

第二种颜色在“红色”和“绿色”之间交替，但你不必事先选择颜色。

如果我分配这个问题，下一个问题将是“假设你只有足够的油漆建造一栋红色的房子”。