[LeetCode] 265. Paint House II

 문제 설명은 아래와 같다.

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

 

 주어진 예시는 아래와 같다.

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.

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

 

 Dynamic Programming을 사용해 풀었다. 인접한 두 집은 같은 색으로 칠하면 안되기 때문에 각 색깔별로 색을 칠하는 경우의 최소 비용(cost)을 계산해 메모이제이션 테이블(Memoizaition Table)에 계속 저장해 나가는 방식을 활용했다.

 

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        ret = 0
        n = len(costs)
        k = len(costs[0])
        dp = [[0 for j in range(k)] for i in range(n)]

        for i in range(k):
            dp[0][i] = costs[0][i]

        for i in range(1, n):
            for j in range(k):
                c = math.inf
                for l in range(k):
                    if l == j:
                        continue
                    if c > dp[i-1][l]:
                        c = dp[i-1][l]
                        cI = l
                dp[i][j] = costs[i][j] + c

        return min(dp[n-1])