Minimum Amount to Paint the Walls

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. The task is to return the minimum amount of money required to paint the n walls.

Examples:

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.

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.

[Expected Approach] Using Memoization - O(n²) time and O(n²) space

The idea is that we want to prioritize using the paid painter for walls that are cheaper and take longer to paint because this will help us to use the free painter to work for longer time. This looks like a greedy problem but formulating into strategy is difficult because each decision impacts subsequent choices. Determining which walls to pay for and which to allocate to the free painter becomes complex. We will use dynamic programming to explore all possible decisions.

Step-by-step approach:

• Let dp(i, remain) represent the minimum cost to paint remain walls starting from index i. There are two base cases:
  • If remain <= 0: All walls are painted, return 0.
  • If i == n: This represents no more walls to assign, return a large value (infinity).
• For the ith wall, we have two options. We can either hire the paid painter for this wall or not hire them.
  • If we hire painter for ith wall then cost would be cost[i] + dp(i + 1, remain - 1 - time[i])
  • If we don't hire for ith wall then cost would be dp(i + 1, remain) and we simply move to the next index.

Below is the implementation of the above approach

#include <bits/stdc++.h>
using namespace std;

// Recursive function to compute minimum cost using DP
int helper(int i, int remain, vector<vector<int>> & memo, 
           vector<int> &cost, vector<int> &time) {
    // Base case: If no more walls need to be painted
    if (remain <= 0) return 0;

    // Base case: No more walls to consider
    if (i == cost.size()) return 1e9;

    // Check if result is already in memo
    if (memo[i][remain] != -1) return memo[i][remain];

    // Option 1: Use paid painter for the ith wall
    int paint = cost[i] + helper(i + 1, remain - 1 
               - time[i], memo, cost, time);

    // Option 2: Skip the ith wall
    int dontPaint = helper(i + 1, remain, memo, cost, 
                           time);

    // Store the minimum of the two options in memo
    memo[i][remain] = min(paint, dontPaint);
    return memo[i][remain];
}

// Initialize memoization and start the DP process
int minCost(vector<int> &cost, vector<int> &time) {
    int n = cost.size();

    // Initialize memo table with -1
    vector<vector<int>> memo(n, vector<int>(n + 1, -1));

    // Start DP from the first wall
    return helper(0, n, memo, cost, time);
}

int main() {
    vector<int> cost1 = {1, 2, 3, 2};
    vector<int> time1 = {1, 2, 3, 2};
    cout << "Minimum cost: " << minCost(cost1, time1) 
         << endl;

    return 0;
}

import java.util.Arrays;

class GfG{

    // Recursive function to compute minimum cost using DP
    static int helper(int i, int remain,
                             int[][] memo, int[] cost,
                             int[] time)
    {
        // Base case: If no more walls need to be painted
        if (remain <= 0)
            return 0;

        // Base case: No more walls to consider
        if (i == cost.length)
            return 1000000000;

        // Check if result is already in memo
        if (memo[i][remain] != -1)
            return memo[i][remain];

        // Option 1: Use paid painter for the ith wall
        int paint = cost[i]
                    + helper(i + 1, remain - 1 - time[i],
                             memo, cost, time);

        // Option 2: Skip the ith wall
        int dontPaint
            = helper(i + 1, remain, memo, cost, time);

        // Store the minimum of the two options in memo
        memo[i][remain] = Math.min(paint, dontPaint);
        return memo[i][remain];
    }

    // Initialize memoization and start the DP process
    static int minCost(int[] cost, int[] time)
    {
        int n = cost.length;

        // Initialize memo table with -1
        int[][] memo = new int[n][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        // Start DP from the first wall
        return helper(0, n, memo, cost, time);
    }

    public static void main(String[] args)
    {
        int[] cost1 = { 1, 2, 3, 2 };
        int[] time1 = { 1, 2, 3, 2 };
        System.out.println("Minimum cost: "
                           + minCost(cost1, time1));
    }
}

# Recursive function to compute minimum cost
def helper(i, remain, memo, cost, time):
    # Base case: No more walls need painting
    if remain <= 0:
        return 0
    # Base case: No more walls to consider
    if i == len(cost):
        return float('inf')

    # Check if result is in memo
    if memo[i][remain] != -1:
        return memo[i][remain]

    # Option 1: Use paid painter for ith wall
    paint = cost[i] + helper(i + 1, remain - 1 
                             - time[i], memo, cost, time)

    # Option 2: Skip the ith wall
    dont_paint = helper(i + 1, remain, memo, cost, time)

    # Store the minimum of the two options in memo
    memo[i][remain] = min(paint, dont_paint)
    return memo[i][remain]

# Function to start the DP process
def min_cost(cost, time):
    n = len(cost)
    # Initialize memo table with -1
    memo = [[-1] * (n + 1) for _ in range(n)]
    # Start DP from the first wall
    return helper(0, n, memo, cost, time)

cost1 = [1, 2, 3, 2]
time1 = [1, 2, 3, 2]
print("Minimum cost:", min_cost(cost1, time1))

function helper(i, remain, memo, cost, time)
{
    // Base case: If no more walls need to be painted
    if (remain <= 0)
        return 0;

    // Base case: No more walls to consider
    if (i === cost.length)
        return Infinity;

    // Check if result is already in memo
    if (memo[i][remain] !== -1)
        return memo[i][remain];

    // Option 1: Use paid painter for the ith wall
    let paint = cost[i]
                + helper(i + 1, remain - 1 - time[i], memo,
                         cost, time);

    // Option 2: Skip the ith wall
    let dontPaint = helper(i + 1, remain, memo, cost, time);

    // Store the minimum of the two options in memo
    memo[i][remain] = Math.min(paint, dontPaint);
    return memo[i][remain];
}

function minCost(cost, time)
{
    let n = cost.length;

    // Initialize memo table with -1
    let memo = Array.from({length : n},
                          () => Array(n + 1).fill(-1));

    // Start DP from the first wall
    return helper(0, n, memo, cost, time);
}

// Example usage
let cost1 = [ 1, 2, 3, 2 ];
let time1 = [ 1, 2, 3, 2 ];
console.log("Minimum cost: " + minCost(cost1, time1));

Minimum cost: 3

Time Complexity: O(n^2), where n is the number of walls.
Auxiliary Space: O(n^2)