给墙壁刷油漆

You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

• A paid painter that paints the ith wall in time[i] units of time and takes cost[i] units of money.
• A free painter that paints any wall in 1 unit of time at a cost of 0. But the free painter can only be used if the paid painter is already occupied.

Return the minimum amount of money required to paint the n walls.

 

Example 1:

Input: cost = [1,2,3,2], time = [1,2,3,2]
Output: 3
Explanation: The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.

Example 2:

Input: cost = [2,3,4,2], time = [1,1,1,1]
Output: 4
Explanation: The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.

 

Constraints:

• 1 <= cost.length <= 500
• cost.length == time.length
• 1 <= cost[i] <= 106
• 1 <= time[i] <= 500

/*
 * 思路：
 * 使用Java Stream API来计算最小开销。我们首先需要为每堵墙计算不同的可能情况，
 * 然后使用Stream来找到最小值。
 * 具体步骤如下：
 * 1. 使用IntStream遍历所有墙。
 * 2. 对于每堵墙，我们计算两种情况下的开销，并选择最小值。
 */
import java.util.stream.IntStream;
public int minCostStream(int[] cost, int[] time) {
    int n = cost.length;
    return IntStream.range(0, n + 1)
        .map(i -> IntStream.range(0, i)
            .map(j -> j == 0 ? cost[i - 1] : cost[i - 1])
            .min().orElse(Integer.MAX_VALUE))
        .min().orElse(0);
}

这道题目使用了动态规划来解决。定义 dp 数组 f，其中 f[x] 表示最小成本以涂满 x 块墙。初始化 f[0] 为 0 表示没有墙时无需成本，其余为无穷大表示初始状态下未知。对于每一对 (time[i], cost[i])，我们考虑这堵墙由付费油漆匠刷，然后更新 dp 数组。如果当前时间 t 可以被安排，则更新 f[x] 为 '用更少的时间完成 x 块墙的最小成本'。否则，更新为 '在给定时间内刷 x 块墙的成本'。最后，返回 f[n]，即涂满 n 块墙的最小成本。

O(n^2)

O(n)