动态规划 —— 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]));
    }
};

---

完结撒花~

原文地址：https://blog.csdn.net/hedhjd/article/details/143612893

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！