动态规划：粉刷房子问题

题目描述

题目链接：LCR 091. 粉刷房子

题目解析

根据图示，costs 数组的行代表房子的编号，列索引分别对应红色（0）、蓝色（1）、绿色（2）。粉刷房子只需保证相邻两个房子颜色不同即可。

算法原理

状态表示

• dp[i][0]：涂到第 i 个位置时，最后一个位置粉刷红色的最小花费。
• dp[i][1]：涂到第 i 个位置时，最后一个位置粉刷蓝色的最小花费。
• dp[i][2]：涂到第 i 个位置时，最后一个位置粉刷绿色的最小花费。

状态转移方程

根据上一步的状态划分问题：

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]

初始化

为了简化边界处理，在 dp 表前增加一个虚拟节点。本题初始化为 0。下标映射关系：由于增加了虚拟节点，原数组下标需统一减 1 进行访问。

填表顺序

从左往右，三个状态同时更新。

返回值

返回最后一个房子三种颜色的最小花费：min(dp[n][0], min(dp[n][1], dp[n][2]))。

代码实现

动态规划的固定四步骤：创建 dp 表、初始化、填表、确定返回值。

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));
        // 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]));
    }
};