油漆房子 - 算法问题

Question

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

有一排n个房子，每个房子都可以涂上三种颜色中的一种：红色，蓝色或绿色。用一定颜色绘制每个房子的成本是不同的。你必须为所有的房屋涂漆，使两个相邻的房屋没有相同的颜色。

用特定颜色绘制每个房屋的成本由n×3成本矩阵表示。例如，成本[0] [0]是用红色绘制房屋0的成本;成本[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

您正在使用贪婪的方法，正如评论中j_random_hacker所述，在所有情况下都找不到最佳解决方案。

您可能会从使用图表方法中受益。

想象一下，成本矩阵的每个单元都是一个节点。然后，每个节点具有将其连接到来自上方和下方的两个不同颜色的单元格的边缘。

那是：

细胞cost[i][j]的边缘连接到cost[i - 1][(j + 1)%3]，cost[i - 1][(j + 2)%3]，cost[i + 1][(j + 1)%3]和cost[i + 1][(j + 2)%3]，所有i在[0，n-1]和j在[0,2]中。

为了简化下一部分，您可以创建两个成本为0的附加节点。一个节点（Start节点）连接到第一行中的所有节点，一个节点（End Node）连接到最后一行中的所有节点。

现在您只需使用Dijkstra的最短路径算法来计算从起始节点到结束节点的最短距离。

Answer 2

你可以使用动态编程找到绘制第一个i房屋的最低成本，假设房子i被涂上颜色j。然后原始问题的解决方案是最终房屋的颜色，这导致最小的总成本。

动态程序是有效的，因为（例如）绘制第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）时间。