Sponsored
Sponsored
This approach uses a dynamic programming strategy to determine the minimum cost. The idea is to leverage a DP array where dp[i] represents the minimum cost to paint up to the i-th wall. For each wall, we decide whether to use only the paid painter or to also utilize the free painter effectively when paid painter is occupied.
Time Complexity: O(n^2), Space Complexity: O(n)
1#include <stdio.h>
2#include <limits.h>
3
4int minCost(int* cost, int* time, int n) {
5 int dp[n+1];
6 int occupied = 0;
7 dp[0] = 0;
8 dp[1] = cost[0];
9
10 for (int i = 2; i <= n; i++) {
11 dp[i] = INT_MAX;
12 for (int j = i-1; j >= 0; j--) {
13 if (occupied >= time[j]) {
14 dp[i] = fmin(dp[i], dp[j] + cost[i-1]);
15 break;
16 }
17 occupied += time[j];
18 }
19 }
20 return dp[n];
21}
22
23int main() {
24 int cost[] = {1, 2, 3, 2};
25 int time[] = {1, 2, 3, 2};
26 int n = sizeof(cost) / sizeof(cost[0]);
27 printf("%d\n", minCost(cost, time, n));
28 return 0;
29}This C solution implements a dynamic programming approach. It uses a 'dp' array where each index i captures the minimum cost to paint walls up to that point. The loop iteratively decides whether to utilize the paid or free painter based on occupancy.
This approach leverages a greedy strategy, prioritizing the choice that minimizes cost per time unit. By sorting or considering smallest cost per time unit, we attempt to reach a solution that overall minimizes the total cost.
Time Complexity: O(n log n), Space Complexity: O(n)
1import java
In this Java solution, a custom Pair class is used, where pairs of cost and time are sorted by their cost/time ratio. This prioritizes walls that are cheaper per unit time, optimizing total cost.