Minimize total cost without repeating same task in two consecutive iterations

0 0 11 minutes read

Given an array arr[][] of size M X N where M represents the number of tasks and N represents number of iteration. An entry in the array arr[i][j] represents the cost to perform task j at the i^th iteration. Given that the same task j cannot be computed in two consecutive iterations, the task is to compute the minimum cost to perform exactly one task in every iteration.
Examples:

Input: N = 4, M = 4, arr[][] = {{4, 5, 3, 2}, {6, 2, 8, 1}, {6, 2, 2, 1}, {0, 5, 5, 1}}
Output: 5
Explanation:

The minimum cost from the array for the first iteration is 2.
Since it is given that the same task cannot be computed in the next iteration, the minimum cost excluding the element at that index is 2. Similarly, the minimum cost for the 3rd iteration is 1 and the 4th iteration is 0. Therefore, the total cost = 2 + 2 + 1 + 0 = 5.
Input: N = 3, M = 2, arr[][] = {{3, 4}, {1, 2}, {10, 0}}
Output: 5

Naive Approach: The naive approach for this problem would be to generate all the possible combinations of tasks and then searching for the combination with minimum cost. However, this will fail for larger sized matrices as the time complexity of this approach would be O(M^N).
Efficient Approach: This problem can be solved efficiently by using the concept of dynamic programming. The intuition is to form a dp-table dp[][] of dimension N x M where dp[i][j] represents the minimum cost of j^th task on i^th iteration. However, since the same task should not be iterated for two consecutive days, the dp table can be filled in the following way:

The 1st row of dp[][] array will be the same as the 1st row of the cost[][] matrix. The answer is the minimum element of the last row.
Below is the implementation of the above approach:

CPP

// C++ implementation of the above approach
// Function to return the minimum cost
// for N iterations
#include <bits/stdc++.h>
using namespace std;
 
int findCost(vector<vector<int>>cost_mat, int N, int M)
{
    // Construct the dp table
    vector<vector<int>> dp(N,vector<int>(M, 0));
     
    // 1st row of dp table will be equal
    // to the 1st of cost matrix
 
    for(int i = 0; i < M; i++)
        dp[0][i] = cost_mat[0][i];
     
    // Iterate through all the rows
    for (int row = 1; row < N; row++){
         
        // To iterate through the
        // columns of current row
        for (int curr_col = 0; curr_col < M; curr_col++)
        {
 
            // Initialize val as infinity
            int val = 999999999;
 
            // To iterate through the
            // columns of previous row
            for(int prev_col = 0; prev_col < M; prev_col++)
            {
 
                if (curr_col != prev_col)
                    val = min(val, dp[row - 1][prev_col]);
            }
             
            // Fill the dp matrix
            dp[row][curr_col] = val + cost_mat[row][curr_col];
        }
        }
 
    // Returning the minimum value
    int ans = INT_MAX;
    for(int i = 0; i < M; i++)
        ans = min(ans, dp[N-1][i]);
    return ans;
}
 
// Driver code
int main()
{
     
// Number of iterations
int N = 4;
 
// Number of tasks
int M = 4;
 
// Cost matrix
vector<vector<int>> cost_mat;
cost_mat = {{4, 5, 3, 2},
            {6, 2, 8, 1},
            {6, 2, 2, 1},
            {0, 5, 5, 1}};
 
cout << findCost(cost_mat, N, M);
return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java implementation of the above approach
// Function to return the minimum cost
// for N iterations
import java.io.*; 
class GFG {
 
    static int findCost(int cost_mat[][], int N, int M)
    {
        // Construct the dp table
        int dp[][] = new int[N][M] ;
        
     
        // 1st row of dp table will be equal
        // to the 1st of cost matrix
 
        for(int i = 0; i < M; i++)
            dp[0][i] = cost_mat[0][i];
     
        // Iterate through all the rows
        for (int row = 1; row < N; row++){
         
            // To iterate through the
            // columns of current row
            for (int curr_col = 0; curr_col < M; curr_col++)
            {
 
                // Initialize val as infinity
                int val = 999999999;
 
                // To iterate through the
                // columns of previous row
                for(int prev_col = 0; prev_col < M; prev_col++)
                {
 
                    if (curr_col != prev_col)
                        val = Math.min(val, dp[row - 1][prev_col]);
                }
             
                // Fill the dp matrix
                dp[row][curr_col] = val + cost_mat[row][curr_col];
            }
            }
 
        // Returning the minimum value
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < M; i++)
            ans = Math.min(ans, dp[N-1][i]);
        return ans;
    }
 
    // Driver code
    public static void main (String[] args)  
    {
     
    // Number of iterations
    int N = 4;
 
    // Number of tasks
    int M = 4;
 
    // Cost matrix
    int cost_mat[][] = {{4, 5, 3, 2},
                {6, 2, 8, 1},
                {6, 2, 2, 1},
                {0, 5, 5, 1}};
 
    System.out.println(findCost(cost_mat, N, M));
     
    }
 
}
 
 
// This code is contributed by ANKITKUMAR34

Python

# Python implementation of the above approach
 
# Function to return the minimum cost 
# for N iterations
def findCost(cost_mat, N, M):
     
    # Construct the dp table
    dp = [[0]*M for _ in range(M)]
     
    # 1st row of dp table will be equal 
    # to the 1st of cost matrix 
    dp[0] = cost_mat[0]
     
      
    # Iterate through all the rows
    for row in range(1, N):
         
        # To iterate through the 
        # columns of current row
        for curr_col in range(M):
             
            # Initialize val as infinity
            val = 999999999
             
            # To iterate through the 
            # columns of previous row
            for prev_col in range(M):
                 
                if curr_col != prev_col: 
                    val = min(val, dp[row-1][prev_col])
                     
            # Fill the dp matrix
            dp[row][curr_col] = val + cost_mat[row][curr_col]
             
    # Returning the minimum value
    return min(dp[-1])
                 
if __name__ == "__main__":
 
    # Number of iterations
    N = 4
     
    # Number of tasks
    M = 4
 
    # Cost matrix
    cost_mat = [[4, 5, 3, 2],
                [6, 2, 8, 1],
                [6, 2, 2, 1],
                [0, 5, 5, 1]]
     
    print(findCost(cost_mat, N, M))
    

C#

// C# implementation of the above approach
// Function to return the minimum cost
// for N iterations
using System;
 
class GFG {
 
    static int findCost(int [,]cost_mat, int N, int M)
    {
        // Construct the dp table
        int [,]dp = new int[N, M] ;
        
     
        // 1st row of dp table will be equal
        // to the 1st of cost matrix
 
        for(int i = 0; i < M; i++)
            dp[0, i] = cost_mat[0, i];
     
        // Iterate through all the rows
        for (int row = 1; row < N; row++){
         
            // To iterate through the
            // columns of current row
            for (int curr_col = 0; curr_col < M; curr_col++)
            {
 
                // Initialize val as infinity
                int val = 999999999;
 
                // To iterate through the
                // columns of previous row
                for(int prev_col = 0; prev_col < M; prev_col++)
                {
 
                    if (curr_col != prev_col)
                        val = Math.Min(val, dp[row - 1, prev_col]);
                }
             
                // Fill the dp matrix
                dp[row, curr_col] = val + cost_mat[row, curr_col];
            }
            }
 
        // Returning the minimum value
        int ans = int.MaxValue;
         
        for(int i = 0; i < M; i++)
            ans = Math.Min(ans, dp[N - 1, i]);
             
        return ans;
    }
 
    // Driver code
    public static void Main (string[] args) 
    {
     
        // Number of iterations
        int N = 4;
     
        // Number of tasks
        int M = 4;
     
        // Cost matrix
        int [,]cost_mat = {{4, 5, 3, 2},
                    {6, 2, 8, 1},
                    {6, 2, 2, 1},
                    {0, 5, 5, 1}};
     
        Console.WriteLine(findCost(cost_mat, N, M));
     
    }
 
}
 
// This code is contributed by Yash_R

Javascript

<script>
 
// Javascript implementation of 
// the above approach
 
// Function to return the minimum cost
// for N iterations
 
    function findCost(cost_mat , N , M) 
    {
        // Construct the dp table
        var dp = Array(N);
        for( i = 0;i<N;i++)
            dp[i] = Array(M).fill(0);
        // 1st row of dp table will be equal
        // to the 1st of cost matrix
 
        for (i = 0; i < M; i++)
            dp[0][i] = cost_mat[0][i];
 
        // Iterate through all the rows
        for (row = 1; row < N; row++) {
 
            // To iterate through the
            // columns of current row
            for (curr_col = 0; curr_col < M; curr_col++) 
            {
 
                // Initialize val as infinity
                var val = 999999999;
 
                // To iterate through the
                // columns of previous row
                for (prev_col = 0; prev_col < M; 
                prev_col++) 
                {
 
                    if (curr_col != prev_col)
                        val = Math.min(val, 
                        dp[row - 1][prev_col]);
                }
 
                // Fill the dp matrix
                dp[row][curr_col] = val + 
                cost_mat[row][curr_col];
            }
        }
 
        // Returning the minimum value
        var ans = Number.MAX_VALUE;
        for (i = 0; i < M; i++)
            ans = Math.min(ans, dp[N - 1][i]);
        return ans;
    }
 
    // Driver code
     
 
        // Number of iterations
        var N = 4;
 
        // Number of tasks
        var M = 4;
 
        // Cost matrix
        var cost_mat = [ [ 4, 5, 3, 2 ], 
                        [ 6, 2, 8, 1 ], 
                        [ 6, 2, 2, 1 ], 
                        [ 0, 5, 5, 1 ] ];
 
        document.write(findCost(cost_mat, N, M));
 
 
// This code contributed by umadevi9616 
 
</script>

Output:

Time Complexity: O(N * M²)
Auxiliary Space: O(N * M), where N and M are the given dimensions of the matrix.

Efficient Approach : using array instead of 2d matrix to optimize space complexity

In previous code we can se that dp[row][curr_col] is dependent upon dp[row-1][curr_col] and dp[row][curr_col] so we can assume that dp[row-1] is previous row and dp[row] is current row.

Implementations Steps :

Create two vectors prev and curr each of size m+1, where n is a given number of tasks.
Initialize them with base cases.
Now In previous code change dp[row] to curr and change dp[row-1] to prev to keep track only of the two main rows.
After every iteration update previous row to current row to iterate further.

Implementation :

C++

// C++ implementation of the above approach
// Function to return the minimum cost
// for N iterations
#include <bits/stdc++.h>
using namespace std;
 
int findCost(vector<vector<int>>cost_mat, int N, int M)
{
     
    // initialize current and previous row of matrix
    vector<int>prev(M+1, 0);
    vector<int>curr(M+1, 0);
     
     
    // initialize prev vector with base case
    for(int i = 0; i < M; i++)
        prev[i] = cost_mat[0][i];
     
    // Iterate through all the rows
    for (int row = 1; row < N; row++){
         
        // To iterate through the
        // columns of current row
        for (int curr_col = 0; curr_col < M; curr_col++)
        {
 
            // Initialize val as infinity
            int val = 999999999;
 
            // To iterate through the
            // columns of previous row
            for(int prev_col = 0; prev_col < M; prev_col++)
            {
 
                if (curr_col != prev_col)
                    val = min(val, prev[prev_col]);
            }
             
            // Fill the curr vector 
            curr[curr_col] = val + cost_mat[row][curr_col];
        }
        prev = curr;
        }
 
    // Returning the minimum value
    int ans = INT_MAX;
    for(int i = 0; i < M; i++)
        ans = min(ans, curr[i]);
    return ans;
}
 
// Driver code
int main()
{
     
// Number of iterations
int N = 4;
 
// Number of tasks
int M = 4;
 
// Cost matrix
vector<vector<int>> cost_mat;
cost_mat = {{4, 5, 3, 2},
            {6, 2, 8, 1},
            {6, 2, 2, 1},
            {0, 5, 5, 1}};
 
cout << findCost(cost_mat, N, M);
return 0;
}

Java

import java.util.*;
 
public class Main {
     
    public static int findCost(int[][] cost_mat, int N, int M) {
        // Initialize current and previous row of matrix
        int[] prev = new int[M+1];
        int[] curr = new int[M+1];
         
        // initialize prev vector with base case
        for(int i = 0; i < M; i++)
            prev[i] = cost_mat[0][i];
         
        // Iterate through all the rows
        for (int row = 1; row < N; row++) {
            // To iterate through the columns of current row
            for (int curr_col = 0; curr_col < M; curr_col++) {
                // Initialize val as infinity
                int val = Integer.MAX_VALUE;
 
                // To iterate through the columns of previous row
                for(int prev_col = 0; prev_col < M; prev_col++) {
                    if (curr_col != prev_col)
                        val = Math.min(val, prev[prev_col]);
                }
                // Fill the curr vector 
                curr[curr_col] = val + cost_mat[row][curr_col];
            }
            prev = curr.clone();
        }
 
        // Returning the minimum value
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < M; i++)
            ans = Math.min(ans, curr[i]);
        return ans;
    }
     
      // Drive code
    public static void main(String[] args) {
        // Number of iterations
        int N = 4;
         
        // Number of tasks
        int M = 4;
         
        // Cost matrix
        int[][] cost_mat = {{4, 5, 3, 2},
                            {6, 2, 8, 1},
                            {6, 2, 2, 1},
                            {0, 5, 5, 1}};
 
        System.out.println(findCost(cost_mat, N, M));
    }
}

Python3

def findCost(cost_mat, N, M):
    # initialize current and previous row of matrix
    prev = [0] * (M + 1)
    curr = [0] * (M + 1)
 
    # initialize prev vector with base case
    for i in range(M):
        prev[i] = cost_mat[0][i]
 
    # Iterate through all the rows
    for row in range(1, N):
        # To iterate through the columns of current row
        for curr_col in range(M):
            # Initialize val as infinity
            val = float('inf')
 
            # To iterate through the columns of previous row
            for prev_col in range(M):
                if curr_col != prev_col:
                    val = min(val, prev[prev_col])
 
            # Fill the curr vector
            curr[curr_col] = val + cost_mat[row][curr_col]
        prev = curr[:]
 
    # Returning the minimum value
    ans = float('inf')
    for i in range(M):
        ans = min(ans, curr[i])
    return ans
 
# Driver code
# Number of iterations
N = 4
 
# Number of tasks
M = 4
 
# Cost matrix
cost_mat = [[4, 5, 3, 2],
            [6, 2, 8, 1],
            [6, 2, 2, 1],
            [0, 5, 5, 1]]
 
print(findCost(cost_mat, N, M))

C#

using System;
using System.Collections.Generic;
 
class Program {
    static int findCost(List<List<int> > cost_mat, int N,
                        int M)
    {
        // initialize current and previous row of matrix
        List<int> prev = new List<int>();
        List<int> curr = new List<int>();
 
        // initialize prev list with base case
        for (int i = 0; i < M; i++) {
            prev.Add(cost_mat[0][i]);
        }
 
        // Iterate through all the rows
        for (int row = 1; row < N; row++) {
            // To iterate through the
            // columns of current row
            for (int curr_col = 0; curr_col < M;
                 curr_col++) {
                // Initialize val as infinity
                int val = 999999999;
 
                // To iterate through the
                // columns of previous row
                for (int prev_col = 0; prev_col < M;
                     prev_col++) {
                    if (curr_col != prev_col) {
                        val = Math.Min(val, prev[prev_col]);
                    }
                }
 
                // Fill the curr list
                curr.Add(val + cost_mat[row][curr_col]);
            }
 
            prev = new List<int>(curr);
            curr.Clear();
        }
 
        // Returning the minimum value
        int ans = int.MaxValue;
        for (int i = 0; i < M; i++) {
            ans = Math.Min(ans, prev[i]);
        }
 
        return ans;
    }
 
    static void Main(string[] args)
    {
        // Number of iterations
        int N = 4;
 
        // Number of tasks
        int M = 4;
 
        // Cost matrix
        List<List<int> > cost_mat = new List<List<int> >() {
            new List<int>() { 4, 5, 3, 2 },
                new List<int>() { 6, 2, 8, 1 },
                new List<int>() { 6, 2, 2, 1 },
                new List<int>() { 0, 5, 5, 1 }
        };
 
        Console.WriteLine(findCost(cost_mat, N, M));
    }
}

Javascript

function findCost(cost_mat, N, M)
{
 
    // initialize current and previous row of matrix
    let prev = new Array(M+1).fill(0);
    let curr = new Array(M+1).fill(0);
 
    // initialize prev vector with base case
    for (let i = 0; i < M; i++)
        prev[i] = cost_mat[0][i];
 
    // Iterate through all the rows
    for (let row = 1; row < N; row++) 
    {
     
        // To iterate through the columns of current row
        for (let curr_col = 0; curr_col < M; curr_col++)
        {
         
            // Initialize val as infinity
            let val = 999999999;
 
            // To iterate through the columns of previous row
            for (let prev_col = 0; prev_col < M; prev_col++) {
                if (curr_col != prev_col)
                    val = Math.min(val, prev[prev_col]);
            }
 
            // Fill the curr vector 
            curr[curr_col] = val + cost_mat[row][curr_col];
        }
        prev = curr.slice();
    }
 
    // Returning the minimum value
    let ans = Infinity;
    for (let i = 0; i < M; i++)
        ans = Math.min(ans, curr[i]);
    return ans;
}
 
// Driver code
// Number of iterations
let N = 4;
 
// Number of tasks
let M = 4;
 
// Cost matrix
let cost_mat = [[4, 5, 3, 2],
                [6, 2, 8, 1],
                [6, 2, 2, 1],
                [0, 5, 5, 1]];
 
console.log(findCost(cost_mat, N, M));

Output

Time Complexity: O(N * M * M)
Auxiliary Space: O(M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!