python - 油漆房子 - 算法问题

Question

这是一个来自 leetcode 的简单问题， https://leetcode.com/problems/paint-house/description/

有一排n间房子，每间房子都可以涂上三种颜色中的一种:红色、蓝色或绿色。用某种颜色粉刷每间房子的成本是不同的。你必须粉刷所有的房子，这样相邻的两间房子的颜色就不会相同。

用 n x 3 成本矩阵表示为每栋房子涂上某种颜色的成本。例如，costs[0][0] 是给房子 0 涂上红色的成本； costs[1][2] 是将房子 1 刷成绿色的成本，依此类推...找到刷完所有房子的最小成本。

根据我对问题的理解，这是我的解决方案，虽然很冗长，但有意如此，

import sys

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if costs is None or len(costs) == 0:
            return 0
        memo = [0 for _ in range(len(costs))]

        house, cost = self.get_min_cost_and_index(costs[0])
        memo[0] = cost
        for i in range(1, len(costs)):
            curr_house, curr_cost = self.get_min_cost_and_index(costs[i])
            if curr_house == house:
                mod_house, mod_cost = self.get_min_cost_and_index_minus_one(costs[i], house)
                memo[i] = memo[i-1] + mod_cost
                house = mod_house
            else:
                memo[i] = memo[i-1] + curr_cost
                house = curr_house

        return memo[-1]

    def get_min_cost_and_index(self, row):
        min_val, index = sys.maxsize, -1
        for i,v in enumerate(row):
            if v < min_val:
                min_val = v
                index = i
        return index, min_val

    def get_min_cost_and_index_minus_one(self, row, minus):
        min_val, index = sys.maxsize, -1
        for i, v in enumerate(row):
            if i == minus:
                continue
            if v < min_val:
                min_val = v
                index = i
        return index, min_val

问题出在下面的测试用例上，它失败了，

if __name__ == '__main__':
    solution = Solution()
    print(solution.minCost([[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]]))

我的解决方案给出了 47，根据我实现的逻辑，这是正确的。正确答案虽然是 43 但我不知道如何以及为什么 有人可以帮我解决我遗漏的问题吗？

Answer 1

假设房子 i 的颜色是 j，您可以使用动态规划找到粉刷前 i 所房子的最小成本。那么原始问题的解决方案就是最终房屋的颜色使总成本​​最小。

动态程序有效，因为(例如)前 10 间房屋将第 10 间房屋涂成红色的最低成本是将第 10 间房屋涂成红色的成本加上将前 9 间房屋涂成第 9 间房屋的最低总成本房子绿色或蓝色。

下面是一个相对简洁的程序来实现这个:

def lowcost(costs):
    c = [0, 0, 0]
    for cc in costs:
        c = [cc[j] + min(c[(j+k)%3] for k in [1, 2]) for j in xrange(3)]
    return min(c)

print(lowcost([[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]]))

它使用 O(1) 内存和 O(N) 时间。