Shopping Offers — LeetCode 638 Python Solution

from functools import lru_cache
from typing import List

def shoppingOffers(price: List[int], special: List[List[int]], needs: List[int]) -> int:
    n = len(price)
    filtered = []
    for sp in special:
        cost = sp[-1]
        if cost < sum(sp[i] * price[i] for i in range(n)):
            filtered.append(sp)

    @lru_cache(None)
    def dfs(state):
        state = list(state)
        best = sum(state[i] * price[i] for i in range(n))
        for sp in filtered:
            nxt = []
            for i in range(n):
                if sp[i] > state[i]:
                    break
                nxt.append(state[i] - sp[i])
            else:
                best = min(best, sp[-1] + dfs(tuple(nxt)))
        return best

    return dfs(tuple(needs))