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
不满足基本情况的调用都会产生三个递归调用,因此调用的数量呈指数增长。所以这不是线性时间解决方案,超过时间限制是正确的。
推荐阅读
- devexpress - DevExpress vs Aspose.pdf
- php - Mediawiki:数据库必须为空或非空字符串
- c# - C# 构造函数和方法
- node.js - 使用 $unwind 获取空数组作为聚合结果
- java - 无法将 Base64 字符串解码为位图
- java - datasnapshot.getvalue() 不起作用并使应用程序崩溃
- angularjs - 在角度选择中选择特定的默认选项
- java - 使用 Java 在 Linux 上查找给定文件的根目录
- azure-pipelines - 如何在特定时间安排 VSTS 中的构建?
- assembly - MIPS 流水线阶段