Leetcode 256. Paint House (Python)

Related Topic

Dynamic-Programming.

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.

Sample I/O

Example 1

Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
Minimum cost: 2 + 5 + 3 = 10.

Note:

All costs are positive integers.

Methodology

This question solved by Dynamic Programming. Each house have three color options and adjacent houses can not be same color.

1. Find the pattern:

   Suppose we choose red color for the current house then the previous adjacent house can only either be blue or green. We gonna choose the minimum cost from those two colors and then add up to my cost of current house with red color. This will be the total min cost from current house to previous house when the current is red.

   If we are not choose red but green for the current house then the previous adjacent house can only either be blue or red. We gonna choose the minimum cost from those two colors and then add up to my cost of current house with green color. This will be the total min cost from current house to previous house when the current is green.

   If we are now choose blue for the current house then the previous adjacent house can only either be red or green. We gonna choose the minimum cost from those two colors and then add up to my cost of current house with blue color. This will be the total min cost from current house to previous house when the current is blue.

2. Extended option:

   Could be more than three colors or every three houses are not same color!

Code 1 (original idea)

def minCost(self, costs: List[List[int]]) -> int:
        size=len(costs)
        if size == 0: return 0
        if size == 1: return min(costs[0])
        for i in range(1,size):
            costs[i][0]+=min(costs[i-1][1],costs[i-1][2])
            costs[i][1]+=min(costs[i-1][0],costs[i-1][2])
            costs[i][2]+=min(costs[i-1][1],costs[i-1][0])
        return min(costs[-1])

Code 2 (simplify the code)

def minCost(self, costs: List[List[int]]) -> int:
        red, blue, green = 0,0,0
            for r, b, g in costs:
                red, blue, green = min(blue, green) + r, min(red, green) + b, min(red, blue) + g
            return min(red, blue, green)

BigO

We iterate all dp list, it will cost O(n), each value will add up last 1 value as result, it will cost (1+1), in total will be O(n+n) and It is O(n)