LCR 091. 粉刷房子

题目

思路描述

动态规划

1. 状态定义：

   • costs[i][j] 表示第 i 个房子粉刷成第 j 种颜色的花费。
   • dp[i][j] 表示前 i 个房子粉刷到第 i 个房子为第 j 种颜色的最小花费。

2. 状态转移方程：

   • dp[i][j] = costs[i][j] + min(dp[i-1][k])，其中 k != j。
   • 即当前房子的颜色不能与前一个房子的颜色相同。

3. 边界条件：

   • 初始化 dp[0][j] = costs[0][j]，表示第一个房子粉刷成第 j 种颜色的花费。

4. 最终结果：

   • 最终结果是 min(dp[n-1][j])，即最后一个房子粉刷成任意一种颜色的最小花费。

代码实现

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;

        int n = costs.size();
        for (int i = 1; i < n; ++i) {
            costs[i][0] += min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += min(costs[i - 1][0], costs[i - 1][1]);
        }

        return min({costs[n - 1][0], costs[n - 1][1], costs[n - 1][2]});
    }
};

注意事项

1. 边界条件处理：

   • 如果 costs 为空，直接返回 0。

2. 变量初始化：

   • 初始化 n 为 costs 的大小。

3. 循环控制：

   • 循环从 1 开始到 n，确保覆盖所有可能的房子数。