剑指 Offer II 091.粉刷房子

【LetMeFly】剑指 Offer II 091.粉刷房子 - 原地修改

力扣题目链接：https://leetcode.cn/problems/JEj789/

假如有一排房子，共 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

 

注意：本题与主站 256 题相同：https://leetcode-cn.com/problems/paint-house/

方法一：动态规划

这是一道比较容易想出来的动态规划，我们用$dp[i][j]$表示第$i + 1$个方块粉刷第$j$个颜色时，前$i + 1$个方块儿的最小花费。

那么，$min{dp[n - 1][0, 1, 2]}$就是答案（把第$n$个方块粉刷成$3$种颜色中的一个，前$n$个方块的最小花费）

但是，相邻两个方块颜色不能相同。因此递推公式：

• $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]$

如果允许修改$costs$数组，那么我们可以直接用$costs$数组来代替$dp$数组，$costs[i][j] += min(costs[i - 1][xx])$即可。

• 时间复杂度$O(n)$，其中$n$是房子个数
• 空间复杂度：
  • 如果能修改$costs$数组，就不需要额外开辟数组空间，只需要使用常数个变量即可，此时空间复杂度为$O(1)$；
  • 如果不能修改$costs$数组，那么 如果额外开辟一个$dp$数组，空间复杂度为$O(n)$；如果使用$3$个变量代替$dp$数组，空间复杂度$O(1)$（因为dp数组第$i-1$之前内容不会再用到）

AC代码

C++

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        for (int i = 1; i < costs.size(); i++) {
            costs[i][0] += min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += min(costs[i - 1][0], costs[i - 1][1]);
        }
        return min(costs[costs.size() - 1][0], min(costs[costs.size() - 1][1], costs[costs.size() - 1][2]));
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125456885