[LeetCode] 265. Paint House II

 Problem : https://leetcode.com/problems/paint-house-ii/

A naive DP solution. 

Time complexity = O ( N * K * K )

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        N = len(costs)
        K = len(costs[0])
        MAX_INT = 2**31 - 1
        
        dp = costs[0]
        
        for i in range(1, N):
            tmp = [MAX_INT] * K
            
            for j in range(K):
                for k in range(K):
                    if j != k:            
                        tmp[j] = min(tmp[j], costs[i][j] + dp[k])
            
            dp = tmp
        
        return min(dp)

Use extra space to find the minimal value of DP except position i. 

Time complexity  = O ( N * K )

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        N = len(costs)
        K = len(costs[0])
        MAX_INT = 2**31 - 1
        
        dp = costs[0]
        
        for i in range(1, N):
            tmp = [MAX_INT] * K
            leftMi = [MAX_INT] * K  # minimum value from left
            rightMi = [MAX_INT] * K # minimum value from right
            
            mi = dp[0]
            for j in range(1, K):
                leftMi[j] = mi
                mi = min(mi, dp[j])
            
            mi = dp[K-1]
            for j in reversed(range(K-1)):
                rightMi[j] = mi
                mi = min(mi, dp[j])
            
            for j in range(K):
                tmp[j] = min(leftMi[j], rightMi[j]) + costs[i][j]
            
            dp = tmp
        
        return min(dp)