做网站的职员称呼什么,搜索引擎优化指的是什么,城市建设协会网站,重庆网站推广什么1. 题目解析
题目链接#xff1a;LCR 091. 粉刷房子 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
2.算法原理
1. 状态定义
在解决这类问题时#xff0c;我们首先需要根据题目的具体要求来定义状态。针对房屋粉刷问题#…1. 题目解析
题目链接LCR 091. 粉刷房子 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
2.算法原理
1. 状态定义
在解决这类问题时我们首先需要根据题目的具体要求来定义状态。针对房屋粉刷问题我们可以定义一个二维数组dp来表示状态其中dp[i][j]表示粉刷到第i个位置时且最后一个位置粉刷成颜色jj可以是红、蓝、绿三种颜色时的最小花费。
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或者一个不会影响后续计算的值。这样做可以确保我们的状态转移方程在i1时也能正确工作。
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(vectorvectorint costs) {int n costs.size();vectorvectorint dp(n 1, vectorint(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
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
