[动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子
[动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子
文章目录
- [动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子
- 题目解析
- 解题思路
- 状态表示
- 状态转移方程
- 初始化和填表顺序
- 返回值
- 代码实现
- 总结
LCR 091. 粉刷房子
题目解析
(1) 一排房子，共有n个
(2) 染红色、蓝色和绿色，且相邻两个房子颜色不能相同
(3) 不同颜色的价格用cost数组表示，大小为n*3
(4) cost[0] [0]，0表示染红色的价格、cost[1] [2]， 2表示染绿色的价格，剩下的1则表示染蓝色的价格
(5) 求出最小价格
示例1：
解题思路
状态表示
按照以往的经验，我们就取以i为终点，所花费的最小的价格
本题的开始有三种不同的染法，第一个位置可以染红色、蓝色或者绿色。
所以dp[i] [0]：表示第一个位置染红色，到i位置的最小价格
dp[i] [1]：表示第一个位置染蓝色，到i位置的最小价格
dp[i] [2]：表示第一个位置染绿色，到i位置的最小价格
状态转移方程
当我们第i个位置染了红色，那么i-1位置就是取蓝色或者绿色的最小价格
所以dp[i] [0] 为到i-1位置两种颜色的较小值加上对应的i位置染红色的价格
所以，可以得出三个状态转移方程
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost对应i位置染红色的价格
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost对应i位置染蓝色的价格
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost对应i位置染绿色的价格
初始化和填表顺序
- 初始化
我们已经确定了三个初始时分别染红色、蓝色和绿色，填上价格即可。
- 填表顺序
三个位置同时从左到右填即可。
返回值
返回三个染法的最小值即可。
看到这里，我们可以自己尝试实现代码，再来看下面的内容。
代码实现
class Solution {
public:int minCost(vector<vector<int>>& costs) {//创建dp数组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]));}
};
总结
细节1：在填表的过程中，会帮我们一并填上0对应位置的价格，所以我们在循环外边不用手动初始化。
细节2：注意下标之间的对应关系，我们从1开始，但是cost表是从0开始的。
细节3：返回值是三者中的最小值。