Paint Houses - Algorithmic problems

Question

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

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.

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]]))

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 don't understand the downvote. It's not a competition or a running challenge, it's a platform to practise coding problem. I have an approach that I've tried and doesn't work correctly and I can't understand why. Which part of SO guidelines have I violated? — Melissa Stewart
From what I can tell (specifically, that you don't seem to be using recursion or (better) dynamic programming), you're using a greedy algorithm. This won't work all the time for this problem, because the optimal overall solution might involve making seemingly "bad" decisions early on, in order to get a big payoff later. As a very simple example, suppose there are just 2 houses, with costs [10, 20, 30] and [1, 500, 500]. Your algorithm will "greedily" choose to paint the first house with colour #1 because 10 < 20 and 10 < 30, but then it's forced to pay 500 for the second house. — j_random_hacker
I don't understand the problem, can you please explain this problem — nitinsridar

Paul Hankin Paul Hankin · Accepted Answer · 2017-07-30T19:40:59

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.

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]]))

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

Paint Houses - Algorithmic problems

2 Answers