Problem statement

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

Solution

Let a, b, c be the minimum costs we can have if we have i-th home painted as green, red and blue respectively. Then we just need to update this values on each step. If we have green for example, it means, that previous was red or blue and we need to choose minimum.

Complexity

Time complexity is $O(n)$, space complexity is $O(1)$.

Code

class Solution:
    def minCost(self, costs):
        a, b, c = 0, 0, 0
        for x, y, z in costs:
            a, b, c = x + min(b, c), y + min(a, c), z + min(a, b)
            
        return min(a, b, c)