不,它不是
NP-hard问题(从技术上讲,“
NP-complete”这个术语对于这个问题是错误的,因为这不是一个决策问题)。
动态规划可行,并且给出O(
n)时间复杂度的算法。(
n是房屋数量)
您需要维护三个数组
R[1..n],B[1..n],G[1..n]
,其中
R[i]
是将房屋1、2、3...
i
涂成红色的最小成本。同样,
B[i]
是将房屋1、2...
i
涂成蓝色的最小成本,而
G[i]
是将房屋1、2...
i
涂成绿色的最小成本。
您可以计算
R[i+1]
:
R[i+1]=(涂第i+1座房子为红色的成本)+最小值{G[i],B[i]}
。
同样地,
B[i+1]
和
G[i+1]
也可以计算出来。
最终,取
R[n],B[n]和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 6 107
G : 0 2 101 8
B : 0 3 101 10
从最后一列,即所有三个房子都被涂色的那一列,我们可以找到最小成本,它等于8并对应组合[绿色(2),红色(4),绿色(2)]。
快速Python:
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]),这是一个导致解决方案的成本矩阵。