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 <iostream>
2#include <vector>
3#include <limits.h>
4using namespace std;
5
6int minCost(vector<int>& cost, vector<int>& time) {
7 int n = cost.size();
8 vector<int> dp(n + 1, INT_MAX);
9 dp[0] = 0;
10
11 for (int i = 0; i < n; ++i) {
12 for (int j = i; j < n; ++j) {
13 if (j == i || time[i] + (j == 0 ? 0 : time[j-1]) <= time[i]) {
14 dp[j + 1] = min(dp[j + 1], dp[i] + cost[j]);
15 }
16 }
17 }
18 return dp[n];
19}
20
21int main() {
22 vector<int> cost = {1, 2, 3, 2};
23 vector<int> time = {1, 2, 3, 2};
24 cout << minCost(cost, time) << endl;
25 return 0;
26}In this solution, we use C++ vectors in the same dynamic programming approach. The dp vector keeps track of the cost incurred for each incremental wall painted, while checking both painters' availability.
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)
1#include
This C greedy approach calculates ratios of cost per time unit and sorts them to choose the painting sequence that increases efficiency, minimizing the cost.