动态规划 —— dp 问题-粉刷房子

1. 剑指offer —— 粉刷房子

题目链接： LCR 091. 粉刷房子 - 力扣（LeetCode）

https://leetcode.cn/problems/JEj789/description/

2. 题目解析

根据上图可以得到costs横坐标（行）是房子的号数，红色的下标是0，蓝色的下标是1，绿色的下标是2，粉刷房子只需要保证相邻的两个颜色不同就行

3. 算法原理

状态表示：以某一个位置为结尾或者以某一个位置为起点 dp[i][0]表示：涂到i位置的时候，最后一个位置粉刷红色，此时的最小花费分 dp[i][1]表示：涂到i位置的时候，最后一个位置粉刷蓝色，此时的最小花费分 dp[i][2]表示：涂到i位置的时候，最后一个位置粉刷绿色，此时的最小花费分

2. 状态转移方程 根据最近的一步来划分问题： 1. dp[i][0]=min(dp[i-1][1] , dp[i-1][2]) + costs[i][0] 2. dp[i][1]=min(dp[i-1][0] , dp[i-1][2]) + costs[i][1] 3. dp[i][2]=min(dp[i-1][1] , dp[i-1][0]) + costs[i][2]

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行 我们可以在前面再额外的加上一个虚拟节点 本题初始化为：0 本题的下标映射关系：因为本题给了一个数组，而我们又额外的加上一个虚拟节点 ，所以我们的下标都统一往右边移动了一位，如果想找回之前对应的位置，那么下标需要进行统一减1

4. 填表顺序 本题的填表顺序是：从左往右，三个表同时填（因为填写原数组第一个节点的值是需要另外两个数组虚拟节点的值）

5. 返回值 ：题目要求 + 状态表示 本题的返回值是：min(dp[n][0], min(dp[n][1], dp[n][2]))

4. 代码

动态规划的固定四步骤：1. 创建一个dp表 2. 在填表之前初始化 3. 填表（填表方法：状态转移方程） 4. 确定返回值

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        //1.  创建一个规模(n+1*3)的dp表
        vector<vector<int>>dp(n + 1, vector<int>(3));//n+1：多加了一个虚拟节点

        //2. 初始化为0，vector默认为0

        //3. 填表（填表方法：状态转移方程）
        for (int i = 1; i <= n; i++)
        {
            //下标都-1是因为数组前面加了一个虚拟节点
            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];
        }
        //4. 确定返回值
        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

完结撒花~