[动态规划] (十四) 简单多状态 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位置染绿色的价格
1
2
3

初始化和填表顺序

• 初始化

我们已经确定了三个初始时分别染红色、蓝色和绿色，填上价格即可。

• 填表顺序

三个位置同时从左到右填即可。

返回值

返回三个染法的最小值即可。

看到这里，我们可以自己尝试实现代码，再来看下面的内容。

---

代码实现

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

细节1：在填表的过程中，会帮我们一并填上0对应位置的价格，所以我们在循环外边不用手动初始化。

细节2：注意下标之间的对应关系，我们从1开始，但是cost表是从0开始的。

细节3：返回值是三者中的最小值。