leetcode
leetcode 2951 ~ 3000
粉刷房子

粉刷房子

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 21 ms, 内存: 16.0 MB


/*
题目思路:
使用Java Stream来解决这个问题,需要在数组上进行转换和归约操作。具体实现方式是通过流操作逐步计算出每个房子涂成三种颜色的最小成本,最后获取最小值。
*/

import java.util.Arrays;

public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0) {
        return 0;
    }
    return Arrays.stream(costs)
        .reduce(new int[]{0, 0, 0}, (prev, cost) -> new int[]{
            Math.min(prev[1], prev[2]) + cost[0],
            Math.min(prev[0], prev[2]) + cost[1],
            Math.min(prev[0], prev[1]) + cost[2]
        })
        .stream()
        .min()
        .get();
}

解释

方法:

此题解采用动态规划的方法来解决粉刷房子的问题。定义三个变量red, blue, green来分别表示粉刷到当前房子时,若当前房子粉刷为红色、蓝色和绿色的最小花费。对于每个房子,我们根据前一个房子的颜色花费来更新这三个变量。例如,如果当前房子选择粉刷为红色,则前一个房子只能是蓝色或绿色,因此当前的红色花费为前一个房子的蓝色和绿色花费的较小者加上当前房子粉刷为红色的花费。同理可得蓝色和绿色的更新公式。这个过程从第一个房子遍历到最后一个房子,最后从三个颜色花费中选择最小的即为结果。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在动态规划解决方案中,如何确保最后选取的颜色方案确实是所有房子都符合颜色不同的规则?
在动态规划解决方案中,每次更新红色、蓝色和绿色花费的状态时,都是基于前一个房子的不同颜色的花费来计算的。例如,如果当前房子选择粉刷为红色,则它的花费是基于前一个房子粉刷为蓝色或绿色的最小花费加上当前房子粉刷红色的成本。这样的状态转移保证了每个房子的颜色与相邻房子的颜色不同。最终,我们从最后一个房子的三种颜色花费中选择最小值,这个值反映了遵循颜色不同规则的最小成本方案。
🦆
题解中提到的动态规划方法是否考虑了可能存在多种具有相同最小成本的粉刷方案?
题解的动态规划方法主要关注于计算最小成本,而不是记录具体的粉刷方案。尽管存在可能有多种不同的粉刷方案达到相同的最小成本,但此方法只计算最小成本的值本身。如果需要获取所有可能的最小成本粉刷方案,需要对算法进行扩展,例如使用回溯法或保存所有最优路径的额外数据结构。
🦆
题解的动态规划过程中,为什么只使用了三个变量(red, blue, green)来存储状态,而不是使用一个数组?
使用三个变量(red, blue, green)来存储状态而不使用数组的主要原因是空间效率和简洁性。每次计算只依赖于前一次的三个状态值,因此,只需要三个变量即可进行状态的更新,无需维护一个更大的数组来存储每个房子的颜色状态。这样做降低了空间复杂度,使算法更为高效而简洁。

相关问题