当前位置：首页 > news >正文

动态规划-LCR 091.粉刷房子-力扣(LeetCode)

news 2025/5/30 15:40:38

一、题目解析

根据题目信息，我们能知道0是红色，1是蓝色，2是绿色，由此我们就能分析如何粉刷了

二、算法原理

1、状态表示

由于只有一排房子所以此时dp[i]表示：到达i位置时，此时的最小花费，但我们发现有三种颜色要粉刷，所以我们需要多加一维表示粉刷的颜色。

dp[i][0]：表示到达i位置时，最后一个位置为红色，此时的最小花费

dp[i][1]：表示到达i位置时，最后一个位置为蓝色，此时的最小花费

dp[i][2]：表示到达i位置时，最后一个位置为绿色，此时的最小花费

2、状态转移方程

由于分析方式类似所以这里只给出以红色为结尾时的状态转移方程

由于最后一个为红色，所以红色是必选的，其他的则是以绿或蓝结尾的最小值

dp[i][0]=min(dp[i-1][1],dp[i-1][2]) +costs[i][0]

dp[i][1]=min(dp[i-1][0],dp[i-1][2]) +costs[i][1]

dp[i][2]=min(dp[i-1][0],dp[i-1][1]) +costs[i][2]

3、初始化

由于要用到dp[i-1][0/1/2]所以可以直接初始化dp[0][0]dp[0][1]dp[0][2]，也可以加三个虚拟节点赋值为0 用于初始化，但需要注意下标的映射关系。

4、填表顺序

从左往右，三个表一起填

5、返回值

由于只粉刷一排房子，所以刷到最后一个房子三个颜色中的最小值返回即可

min(dp[n][0],min(dp[n][1],dp[n][2]))

动手实现代码，才能未来助你一臂之力，链接：LCR 091. 粉刷房子 - 力扣（LeetCode）

三、代码示例

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][0],dp[i-1][1])+costs[i-1][2];//绿色}return min(dp[n][0],min(dp[n][1],dp[n][2]));}
};