Today's Challenge

https://leetcode.com/problems/paint-house-iii/

Paint House III - LeetCode

DP로 푸는 문제..
일단 솔루션만 실행 해봄.

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        dp = [[[math.inf for k in range(target + 1)] for j in range(n + 1)] for i in range(m + 1)]
        for j in range(n + 1):
            dp[0][j][0] = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):			    
                if houses[i - 1] and houses[i - 1] != j:
                    continue
                for k in range(1, target + 1):
                    ls = [dp[i - 1][jj][k - 1] for jj in range(1, n + 1) if jj != j] + [dp[i - 1][j][k]]
                    dp[i][j][k] = min(ls)
                    if houses[i - 1] == 0:
                        dp[i][j][k] += cost[i - 1][j - 1]
        ans = min([dp[m][j][target] for j in range(1, n + 1)])
        if ans == math.inf:
            return -1
        return ans