面试必看：粉刷房子问题

粉刷房子问题（动态规划）详细题解

一、题目描述

有一排共n个房子，每个房子可以粉刷成红色、蓝色、绿色三种颜色之一，要求相邻的两个房子颜色不能相同。

每个房子粉刷成不同颜色的成本由一个n*3的正整数矩阵costs表示：

• costs[i][0]：第i个房子粉刷成红色的成本
• costs[i][1]：第i个房子粉刷成蓝色的成本
• costs[i][2]：第i个房子粉刷成绿色的成本

需要计算粉刷完所有房子所需的最小花费成本。

二、问题分析

本题属于典型的动态规划问题，核心特征如下：

1. 求解连续数组的目标最小值
2. 第i个房子的最小累计成本，可由第i-1个房子的状态推导得出
3. 问题满足最优子结构性质，当前最优依赖于前一步的最优

由于相邻房子颜色不能相同，因此：

• 若第i个房子刷红色，则第i-1个只能是蓝色或绿色
• 若第i个房子刷蓝色，则第i-1个只能是红色或绿色
• 若第i个房子刷绿色，则第i-1个只能是红色或蓝色

我们只需分别维护刷三种颜色的最小累计成本即可。

三、解题思路

1. 状态定义

   • red：当前房子粉刷成红色时，前i个房子的最小累计成本
   • blue：当前房子粉刷成蓝色时，前i个房子的最小累计成本
   • green：当前房子粉刷成绿色时，前i个房子的最小累计成本

2. 状态转移

   • 当前刷红色：前一个只能是蓝色或绿色，取两者最小值加上当前红色成本
   • 当前刷蓝色：前一个只能是红色或绿色，取两者最小值加上当前蓝色成本
   • 当前刷绿色：前一个只能是红色或蓝色，取两者最小值加上当前绿色成本

3. 结果
   遍历结束后，三种颜色最终成本中的最小值即为答案。

四、代码实现（C++）

classSolution{public:intminCost(vector<vector<int>>&costs){intn=costs.size();if(n==0)return0;// 初始状态：第一个房子分别刷三种颜色的成本intred=costs[0][0];intblue=costs[0][1];intgreen=costs[0][2];for(inti=1;i<n;i++){// 先保存上一轮状态inttmp_red=red;inttmp_blue=blue;inttmp_green=green;// 当前颜色 = 上一轮另外两种颜色的最小成本 + 当前颜色成本red=min(tmp_blue,tmp_green)+costs[i][0];blue=min(tmp_red,tmp_green)+costs[i][1];green=min(tmp_red,tmp_blue)+costs[i][2];}// 取三种方案的最小值returnmin(red,min(blue,green));}};

五、复杂度分析

• 时间复杂度：O(n)
  只需遍历一次所有房子，共n个房子，每次操作均为常数时间。

• 空间复杂度：O(1)
  仅使用了若干个变量保存状态，没有使用额外的数组或容器。