油漆房-算法问题 [英] Paint Houses - Algorithmic problems

问题描述

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

Here's a simple question from leetcode, https://leetcode.com/problems/paint-house/description/

一排n座房屋，每座房屋可以用以下三种颜色之一绘画:红色，蓝色或绿色.用某种颜色为每所房子涂油漆的成本是不同的.您必须对所有房屋进行粉刷，以使两个相邻的房屋都没有相同的颜色.

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

用n x 3的成本矩阵表示用某种颜色粉刷每所房屋的成本.例如，costs [0] [0]是将房子0涂成红色的成本；cost [1] [2]是将房子1涂成绿色的成本，依此类推...找到油漆所有房屋的最低成本.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

根据我对问题的理解，这是我的解决方案，它很冗长，但有意这样做，

Based on my understanding of the problem, here's my solution, which is verbose, but intentionally so,

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

问题出在下面的测试用例上，

The problem is on the test case below it fails,

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 ，我不知道如何以及为什么有人可以帮我我所缺少的东西吗?

My solution gives 47 which is correct as per the logic I've implemented. The correct answer though is 43 and I can't how and why Can someone help me what I'm missing out?

推荐答案

您可以使用动态编程来查找粉刷第一本 i 房屋的最低成本，并假设房屋 i 涂成 j 的颜色.然后，解决原始问题的方法就是最终房子的颜色，从而使总成本降至最低.

You can use dynamic programming to find the minimum cost of painting the first i houses, assuming house i is painted color j. Then the solution to the original problem is the color of the final house that results in the minimal total cost.

动态程序起作用，因为(例如)将第10栋房屋涂成红色的前10栋房屋的最低成本是将第10栋房屋涂成红色的成本，加上用第9栋房屋涂成第9栋房屋的最低总成本房子是绿色或蓝色.

The dynamic program works, because (for example) the minimum cost of the first 10 houses painting the 10th house red is the cost of painting the 10th house red, plus the minimum total cost of painting the first 9 houses with the 9th house green or blue.

这是一个相对简洁的程序，可以实现以下目的:

Here's a relatively terse program that implements this:

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)时间.

It uses O(1) memory and O(N) time.

这篇关于油漆房-算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！