「动态规划」如何求粉刷房子的最少花费？

LCR 091. 粉刷房子https://leetcode.cn/problems/JEj789/description/

假如有一排房子，共n个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。例如，costs[0][0]表示第0号房子粉刷成红色的成本花费；costs[1][2]表示第1号房子粉刷成绿色的花费，以此类推。请计算出粉刷完所有房子最少的花费成本。

1. 输入：costs = [[17,2,17],[16,16,5],[14,3,19]]，输出：10，解释：将0号房子粉刷成蓝色，1号房子粉刷成绿色，2号房子粉刷成蓝色。最少花费：2 + 5 + 3 = 10。
2. 输入：costs = [[7,6,2]]，输出：2

提示：costs.length == n，costs[i].length == 3，1 <= n <= 100，1 <= costs[i][j] <= 20。

---

我们用动态规划的思想来解决这个问题。

确定状态表示：根据经验和题目要求，我们用dp[i]表示粉刷完i位置的房子后，此时的最少花费。这可以细分为：

• 用dp[i][0]表示：将i位置的房子粉刷成红色之后的最少花费。
• 用dp[i][1]表示：将i位置的房子粉刷成蓝色之后的最少花费。
• 用dp[i][2]表示：将i位置的房子粉刷成绿色之后的最少花费。

简单来说，在dp[i][j]中，i表示最后一个粉刷的房子的编号；j表示最后一个粉刷的房子中，粉刷的颜色的编号；dp[i][j]表示此时的最少花费。

推导状态转移方程：我们考虑最近的一步，即粉刷完i - 1位置的房子之后的情况。

• 考虑dp[i][0]。把i位置的房子粉刷成红色，所以只能把i - 1位置的房子粉刷成蓝色或者绿色。那么，把i位置的房子粉刷成红色之后的最少花费，就应该是把i - 1位置的房子粉刷成蓝色或者绿色之后的最少花费，两种情况的较小值，再加上把i位置粉刷成红色的花费。即dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]。
• 同理，dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]，dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]。

综上所述：dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]，dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]，dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]。

初始化：根据状态转移方程，在计算dp[0][j]，其中j的范围是[0, 2]时，会发生越界访问，所以要进行相应的初始化。

• dp[0][0]表示把0位置的房子粉刷成红色后，此时的最少花费，显然dp[0][0] = costs[0][0]。
• 同理dp[0][1] = costs[0][1]，dp[0][2] = costs[0][2]。

综上所述：dp[0][0] = costs[0][0]，dp[0][1] = costs[0][1]，dp[0][2] = costs[0][2]。

当然，我们可以在最前面添加一个辅助结点dp[0][j] = 0，其中j的范围是[0, 2]。这样，根据状态转移方程，以dp[i][0]为例，此时min(dp[0][1], dp[0][2]) = 0，辅助结点的值不影响结果，符合预期。

填表顺序：根据状态转移方程，对于dp[i][j]只依赖于dp[i - 1][j]，j的范围是[0, 2]。那么，我们只需要沿着i增大的方向填表。

返回值：由于不确定把最后一个房子粉刷成什么颜色，根据状态表示，最终应返回把最后一个房子粉刷成红色、蓝色或者绿色这3种情况中，最少花费的最小值，即dp[n][j]的最小值，其中j的范围是[0, 2]。

细节问题：由于新增了一个辅助结点，此时dp表的规模就不是n x 3，而是(n + 1) x 3。同时需注意下标的映射关系，dp[i][j]对应的是costs[i - 1][j]。

时间复杂度：O(N)，空间复杂度：O(N)。

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();// 创建dp表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]));}
};