难度: Medium
Submission
运行时间: 25 ms
内存: 16.1 MB
# f(n, 0): 粉色最小花费; f(n, 1): 蓝色最小花费; f(n, 2): 绿色最小花费
# f(n, 0) = min(f(n-1, 1), f(n-1, 2)) + cost(n, 0)
# f(0, i) = cost(0, i)
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
dp = costs[0]
for cost in costs[1:]:
newDp = [0, 0, 0]
newDp[0] = min(dp[1], dp[2]) + cost[0]
newDp[1] = min(dp[0], dp[2]) + cost[1]
newDp[2] = min(dp[0], dp[1]) + cost[2]
dp = newDp
return min(dp)
Explain
这个题解使用动态规划的方法来求解最小花费。定义 dp[i][j] 表示粉刷前 i 个房子，且第 i 个房子使用颜色 j 的最小花费。状态转移方程为：dp[i][j] = min(dp[i-1][k]) + costs[i][j]，其中 k != j。边界条件为 dp[0][j] = costs[0][j]。最终答案为 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])，即粉刷完所有房子时的最小花费。为了优化空间复杂度，可以只使用一维数组来存储状态，即 dp[j] 表示粉刷当前房子使用颜色 j 的最小花费。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
# 初始化 dp 数组，表示粉刷第一个房子的最小花费
dp = costs[0]
# 遍历每个房子
for cost in costs[1:]:
newDp = [0, 0, 0]
# 粉刷当前房子使用红色的最小花费
newDp[0] = min(dp[1], dp[2]) + cost[0]
# 粉刷当前房子使用蓝色的最小花费
newDp[1] = min(dp[0], dp[2]) + cost[1]
# 粉刷当前房子使用绿色的最小花费
newDp[2] = min(dp[0], dp[1]) + cost[2]
# 更新 dp 数组
dp = newDp
# 返回粉刷完所有房子的最小花费
return min(dp)
Explore
在动态规划的粉刷房子问题中，初始化`dp`数组的边界情况对于正确地启动算法非常关键。边界情况指的是粉刷第一个房子的最小花费。由于第一个房子没有前一个房子，所以它的花费直接等于各个颜色的成本。具体而言，`dp[0]`、`dp[1]`和`dp[2]`分别初始化为第一个房子使用红色、蓝色和绿色的成本，即`costs[0][0]`、`costs[0][1]`和`costs[0][2]`。这样初始化确保了从第二个房子开始的状态转移能够基于这个精确的基础进行计算。
在题解中，状态转移方程`dp[i][j] = min(dp[i-1][k]) + costs[i][j]`中的约束`k != j`是通过在计算每个颜色的最小花费时排除当前颜色实现的。具体来说，当计算新的花费`newDp[0]`（粉刷当前房子为红色的花费）时，代码中使用`min(dp[1], dp[2])`来确保不考虑上一个房子也是红色的情况，这是因为`dp[1]`和`dp[2]`分别代表上一个房子粉刷为蓝色和绿色的最小花费。同理，计算`newDp[1]`和`newDp[2]`时，也分别排除了当前颜色，确保满足`k != j`的条件。
在更新`dp`数组时使用一个新数组`newDp`是为了保证在整个更新过程中，每次计算都使用的是上一轮的数据，而不是被当前轮次的更新影响的数据。如果直接在原有的`dp`数组上修改，那么计算`dp[j]`时可能会使用到已经被更新的`dp[k]`值，这会导致计算错误，因为状态转移依赖于前一状态的所有颜色的最小值。使用`newDp`数组确保在整个循环中，每个颜色的最小花费都是基于相同时间点的状态，从而保证了计算的准确性和动态规划的正确实现。