LeetCode «Paint House»: превышен лимит времени, несмотря на решение O (N)? - PullRequest
Новая
       80

LeetCode «Paint House»: превышен лимит времени, несмотря на решение O (N)?

0 голосов
/ 20 сентября 2018

Я пытаюсь решить проблему Paint House на LeetCode.Вот мое попытанное решение: 

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?

1 Ответ

0 голосов
/ 20 сентября 2018

Я только что понял, что каждый вызов minCost, который не удовлетворяет базовым сценариям, генерирует три рекурсивных вызова, так что количество вызовов увеличивается в геометрической прогрессии.Так что это не решение с линейным временем, и правильно, что ограничение по времени превышено.

...