265.Paint House II

Tags: [recursion], [dp], [top_to_bottom_dp], [convert_global_var_recursion_to_return_recursion]

Com: {fb}

Link: https://leetcode.com/problems/paint-house-ii/#/description

There are a row of n houses, each house can be painted with one of the k colors. 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 nxkcost matrix. For example,costs[0][0]is the cost of painting house 0 with color 0;costs[1][2]is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it inO(nk) runtime?

Solution: DP, Top To Bottom DP

class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if not costs or not costs[0]:
            return 0

        num_of_houses = len(costs)
        num_of_colors = len(costs[0])

        memo = {}
        return self.min_cost_helper(num_of_houses, num_of_colors, costs, 0, -1, memo)

    def min_cost_helper(self, num_of_houses, num_of_colors, costs, index, prev_house_color, memo):
        state = '{}:{}'.format(index, prev_house_color)
        if state in memo:
            return memo[state]

        # base case
        if index == num_of_houses - 1:
            min_cost = sys.maxint
            for color in xrange(num_of_colors):
                if color != prev_house_color:
                    min_cost = min(min_cost, costs[index][color])
            return min_cost

        min_cost = sys.maxint
        for color in xrange(num_of_colors):
            if color == prev_house_color:
                continue

            curr_cost = costs[index][color]
            remaining_min_cost = self.min_cost_helper(num_of_houses, num_of_colors, costs, index + 1, color, memo)
            total_curr_min_cost = curr_cost + remaining_min_cost
            min_cost = min(min_cost, total_curr_min_cost)

        memo[state] = min_cost
        return min_cost

Revelation:

• There existing overlapping computation, think about that we have compute to the index = 3, and prev_house_color = 1, there are many ways to let use get to this state, for example, the previous 3 houses can be painted as [3, 2, 1], so the 4th house (whose index = 3)'s prev_house_color = 1, or the previous 3 houses can be painted as [4, 3, 1], so the 4th house's prev_house_color = 1. 看是否存在重复计算，可以站在当前的state往前看，看有没有多种可能达到当前的state.
• 这道题我最先想到的解法是用一个‘全局’ 变量 self.mincost 来跟踪最小的cost，recursion function不返回值，recursion过完所有的可能后，最小的cost，就存在self.min_cost里，但这种recursion没办法用memo，所以我下一个想法就是把这种无返回值的recursion改写成返回值的recursion，我们要求的是一堆房子涂完颜色后最小的cost，那么我们就可以定义recursion就返回一堆房子涂完颜色后最小的cost，但给哪些房子涂颜色是可以通过传参数来config的，这样我们就可以把一个大问题，一层一层的分成很多的sub problem了，最小的problem是，如果只有一个房子，怎么涂颜色cost最小，然后如果两个房子呢， 如果有一堆房子，我们可以每次只看怎么给当前的房子涂颜色，然后让这个recursion给出剩下房子涂完颜色最小的总cost.

Note:

• Time complexity = O(n*k), n is the number of houses, k is the number of colors. Because each index and each color we only compute once to fill the memo.