python - LeetCode“油漆屋”问题:尽管有O(N)解决方案，但超过了时间限制？

我正试图解决LeetCode上的Paint House问题以下是我尝试的解决方案：

import math


class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if not costs:
            return 0
        if len(costs) == 1:
            return min(costs[0])
        return min(costs[0][color] + self.minCost(
            [exclude(costs[1], color), *costs[2:]])
            for color in range(3))


def exclude(arr, color):
    new_arr = arr.copy()
    new_arr[color] = math.inf
    return new_arr

基本上，在每套房子里，它都会考虑为每套房子选择每种颜色的成本，并排除为下一套房子选择的成本（通过将成本设置为无穷大）我认为这应该是线性时间，因为递归调用一直进行到costs数组结束。
我错了吗该解决方案是否具有正确的时间复杂性，但只是比LeetCode施加的时间慢一点？

最佳答案

我刚刚意识到，对不满足基本情况的minCost的每个调用都会生成三个递归调用，从而使调用的数量呈指数增长所以这不是线性时间解，超过时间限制是正确的。