油漆房屋-算法问题

Question

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

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

用n×3的成本矩阵来表示用某种颜色粉刷每所房子的成本。例如，cost是用红色粉刷房子0的成本；costs1是用绿色粉刷房子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，您可以使用动态编程来找到粉刷第一个i房屋的最低成本。然后，原始问题的解决方案是最终房屋的颜色，从而产生最小的总成本。

动态程序是有效的，因为(例如)前10所房屋将第10所房屋涂成红色的最低成本是将第10所房屋涂成红色的成本，加上将前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)时间。

Answer 2

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

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

假设成本矩阵的每个单元格都是一个节点。然后，每个节点都有边从上到下连接到与它不同颜色的两个单元格。

这就是：

对于0中的所有i，n-1和0，2中的j，单元格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]的边。

为了简化下一部分，您可以创建两个成本为0的额外节点。一个节点(开始节点)连接到第一行中的所有节点，另一个节点(结束节点)连接到最后一行中的所有节点。

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