265. Paint House II

LeetCode 265. 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 an n x k cost matrix costs.

• 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...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5

Constraints:

• costs.length == n

• costs[i].length == k

• 1 <= n <= 100

• 1 <= k <= 20

• 1 <= costs[i][j] <= 20

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

Tags

Dynamic Programming

Solution

The basic idea is inherited from LeetCode 256. Paint House. However, when we need to calculate the minimum number for each cur[i], the time overhead would be O(k²). To save it from repeated minimum value computing, we obtain the the two smallest numbers in pre before we update cur. Let's say that the minimum value of pre is first and its index is i, and the last but one minimum number is called second. We can find that all elements apart from cur[i] share the same minimum value first, and the minimum value in terms of cur[i] is second. In this way, we manage to optimize the time complexity from O(nk²) to O(nk).

Complexity

• Time complexity: $O(nk)$

• Space complexity: $O(k)$

Code

type pair struct {
	num, idx int
}

func minCostII(costs [][]int) int {
	ans, cur, pre := 2147483647, make([]int, len(costs[0])), costs[len(costs)-1]
	for i := len(costs) - 2; i >= 0; i-- {
		copy(cur, costs[i])
		first, second := minTwo(pre)
		for j := 0; j < len(cur); j++ {
			if j != first.idx {
				cur[j] += first.num
			} else {
				cur[j] += second.num
			}
		}
		copy(pre, cur)
	}
	for _, n := range pre {
		if n < ans {
			ans = n
		}
	}
	return ans
}

func minTwo(nums []int) (pair, pair) {
	first, second := pair{2147483647, -1}, pair{2147483647, -1}
	for i, n := range nums {
		if n < first.num {
			second.num, second.idx = first.num, first.idx
			first.num, first.idx = n, i
		} else if n < second.num {
			second.num, second.idx = n, i
		}
	}
	return first, second
}