Problem statement

https://binarysearch.com/problems/Painting-Houses/

Solution

Equal to Leetcode 0265. Paint House II

Complexity

Time complexity is O(nk), space complexity can be done in O(k), if we use only last row of matrix, as I did in the following code.

Code

class Solution:
    def solve(self, costs):
        n, k = len(costs), len(costs[0])
        if k == 1 and n == 1: return costs[0][0]
        dp = [0]*k
        
        for cost in costs:
            dp_new = [0]*k
            min_ind = dp.index(min(dp))
            for i in range(k):
                if i != min_ind:
                    dp_new[i] = dp[min_ind] + cost[i]
                else:
                    dp_new[i] = min(dp[i] for i in range(k) if i != min_ind) + cost[i]
                    
            dp = dp_new
            
        return min(dp)