1473. Paint House III

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

use lru cache 50% faster

from functools import lru_cache
class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        @lru_cache(None)
        def dp(i,color,partition):
            if partition > target:
                return float("inf")
            if i == m:
                if partition == target:
                    return 0
                else:
                    return float("inf")
            
            if houses[i]:
                return dp(i+1,houses[i],partition+(houses[i] != color))
            res = float("inf")
            for c, currCost in enumerate(cost[i],1):
                res = min(res,currCost + dp(i+1,c,partition + (c != color)))
            return res
        
        ans = dp(0,0,0)
        if ans == float("inf"):
            return -1
        return ans

self made cache dictionary 25% faster

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        self.cache = dict()
        def dp(i,color,partition):
            if (i,color,partition) in self.cache:
                return self.cache[(i,color,partition)]
            if partition > target:
                self.cache[(i,color,partition)] = float("inf")
                return float("inf")
            if i == m:
                if partition == target:
                    self.cache[(i,color,partition)] = 0
                    return 0
                else:
                    self.cache[(i,color,partition)] = float("inf")
                    return float("inf")
            
            if houses[i]:
                return dp(i+1,houses[i],partition+(houses[i] != color))
            res = float("inf")
            for c, currCost in enumerate(cost[i],1):
                res = min(res,currCost + dp(i+1,c,partition + (c != color)))
            self.cache[(i,color,partition)] = res
            return res
        
        ans = dp(0,0,0)
        if ans == float("inf"):
            return -1
        return ans