我正在尝试解决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 施加的时间限制慢一点?
相关分类