1. 题目解析
题目链接:LCR 091. 粉刷房子
这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。
2.算法原理
1. 状态定义
在解决这类问题时,我们首先需要根据题目的具体要求来定义状态。针对房屋粉刷问题,我们可以定义一个二维数组dp
来表示状态,其中dp[i][j]
表示粉刷到第i
个位置时,且最后一个位置粉刷成颜色j
(j
可以是红、蓝、绿三种颜色)时的最小花费。
dp[i][0]
:表示粉刷到第i
个位置时,最后一个位置粉刷成红色的最小花费。dp[i][1]
:表示粉刷到第i
个位置时,最后一个位置粉刷成蓝色的最小花费。dp[i][2]
:表示粉刷到第i
个位置时,最后一个位置粉刷成绿色的最小花费。
2. 状态转移方程
接下来,我们需要根据题目要求来推导状态转移方程。由于题目中规定了相邻位置不能粉刷成相同的颜色,因此在计算dp[i][j]
时,我们需要考虑i-1
位置的颜色,并确保与j
不同。
- 对于
dp[i][0]
(即第i
个位置粉刷成红色):- 由于不能与前一个位置颜色相同,所以前一个位置可以是蓝色或绿色。因此,状态转移方程为:
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0]
,其中costs[i-1][0]
表示第i-1
个位置粉刷成红色的花费。
- 由于不能与前一个位置颜色相同,所以前一个位置可以是蓝色或绿色。因此,状态转移方程为:
- 同理,对于
dp[i][1]
和dp[i][2]
,我们也可以得到相应的状态转移方程:dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2]
3. 初始化
在填表之前,我们需要对状态数组进行初始化。由于题目没有明确指出第一个位置之前的颜色,我们可以添加一个辅助节点,并将所有颜色在该节点的花费初始化为0(或者一个不会影响后续计算的值)。这样做可以确保我们的状态转移方程在i=1
时也能正确工作。
4. 填表顺序
根据状态转移方程,我们可以发现每个状态dp[i][j]
都依赖于前一个位置的状态dp[i-1][k]
(其中k
不等于j
)。因此,我们需要按照从左到右的顺序来填表,以确保在计算每个状态时,其依赖的状态已经被计算出来。
5. 返回值
最后,我们需要返回粉刷完整个房屋(即最后一个位置)时的最小花费。由于我们定义了三种颜色的状态,因此需要比较这三种颜色在最后一个位置的最小花费,并返回其中的最小值。即:min(dp[n][0], min(dp[n][1], dp[n][2]))
,其中n
是房屋的总位置数。
3.代码编写
class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();vector<vector<int>> dp(n + 1, vector<int>(3));for (int i = 1; i <= n; i++) {dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];}return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};
The Last
嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。
觉得有点收获的话,不妨给我点个赞吧!
如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~