难度: Hard
Submission
运行时间: 32 ms
内存: 16.8 MB
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
dp=[1e9]*len(costs[0])
min_=1e9
mind=-1
smin_=1e9
smind=-1
for i in range(len(costs)):
new_min_=1e9
new_mind=-1
new_smin_=1e9
new_smind=-1
for j in range(len(costs[0])):
if i==0:
dp[j]=costs[i][j]
else:
dp[j]=min_+costs[i][j] if j!=mind else smin_+costs[i][j]
if dp[j]<new_min_:
new_smin_=new_min_
new_smind=new_mind
new_min_=dp[j]
new_mind=j
elif new_min_<=dp[j]<new_smin_:
new_smin_=dp[j]
new_smind=j
min_=new_min_
mind=new_mind
smin_=new_smin_
smind=new_smind
return min_
Explain
这个题解使用了动态规划的思路。定义 dp[j] 表示粉刷第 i 个房子时，第 i-1 个房子使用颜色 j 的最小花费。对于第 i 个房子，遍历每个颜色 j，若第 i-1 个房子使用最小花费的颜色不是 j，则 dp[j] = min_ + costs[i][j]，否则 dp[j] = smin_ + costs[i][j]，其中 min_ 和 smin_ 分别表示上一轮的最小花费和次小花费。然后更新当前轮的 min_、smin_、mind 和 smind。最后返回最后一轮的最小花费 min_ 即可。
时间复杂度: O(nk)
空间复杂度: O(k)
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
dp=[1e9]*len(costs[0])
min_=1e9
mind=-1
smin_=1e9
smind=-1
for i in range(len(costs)):
new_min_=1e9
new_mind=-1
new_smin_=1e9
new_smind=-1
for j in range(len(costs[0])):
if i==0:
dp[j]=costs[i][j] # 第一个房子直接使用对应颜色的花费
else:
# 若第 i-1 个房子使用最小花费颜色不是 j，则使用 min_，否则使用 smin_
dp[j]=min_+costs[i][j] if j!=mind else smin_+costs[i][j]
# 更新当前轮的最小花费、次小花费及其对应的颜色
if dp[j]<new_min_:
new_smin_=new_min_
new_smind=new_mind
new_min_=dp[j]
new_mind=j
elif new_min_<=dp[j]<new_smin_:
new_smin_=dp[j]
new_smind=j
# 更新变量
min_=new_min_
mind=new_mind
smin_=new_smin_
smind=new_smind
return min_ # 返回最后一轮的最小花费
Explore
在动态规划中使用min_和smin_存储最小和次小花费的主要优势在于处理状态转移时的效率。当更新当前房子的染色成本时，如果当前房子选择的颜色与前一个房子的最小成本颜色相同，我们需要使用次小成本来避免颜色重复。如果我们不提前记录次小值，每次计算时都需要重新遍历数组以寻找次小值，这将大大增加计算复杂度。通过记录下最小和次小值，我们可以在O(1)的时间复杂度内完成这一步，从而使整体算法效率更高。
这种设计的理由是为了避免颜色的重复使用。如果当前房子选择的颜色j与前一个房子的最小花费颜色相同（即j == mind），按照题目要求，不能选择相同颜色，因此这种情况下我们应该使用次小成本smin_来计算当前房子的成本。如果使用min_，则可能违反颜色不重复的规则，导致错误的计算结果。
算法通过在每个房子的颜色遍历过程中维护新的最小值new_min_和次小值new_smin_实现这一点。对于每种颜色的成本计算完成后，我们比较并更新new_min_和new_smin_。遍历完所有颜色后，将这些新计算的值赋值给min_和smin_，从而确保在下一轮计算中，min_和smin_正确地代表了所有颜色中的最小和次小花费。这个过程是在每一轮房子的颜色计算中重复进行的，确保了每次循环后的准确性。
在只有一个房子或一个颜色的情况下，算法简化如下：如果只有一个颜色，无论房子数量多少，每个房子只能使用这一种颜色，因此花费是所有房子该颜色成本的总和。如果只有一个房子，那么这个房子可以选择任何一种颜色中的最小成本。在程序实现时，这些情况自然会在遍历中处理，例如当只有一个颜色时，min_始终是这个颜色的成本，smin_无需考虑；当只有一个房子时，直接取这个房子所有颜色中的最小值即可。