[动态规划] (十四) 简单多状态 LeetCode LCR 091.粉刷房子-CSDN博客

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返回值是三者中的最小值。