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 ith 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(MN).
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 jth task on ith iteration. However, since the same task should not be iterated for two consecutive days, the dp table can be filled in the following way:
![dp[i][j] = cost[i][j] + \min_{j!=k}(dp[i-1][k])](https://neveropen.co.uk/wp-content/uploads/2023/11/rubhabha_quicklatex.com-546219ecdbbb4332161e5504f416984e_l3.png "Rendered by QuickLaTeX.com")
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 codeint main(){ // Number of iterationsint N = 4;// Number of tasksint M = 4;// Cost matrixvector<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 iterationsimport 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 iterationsdef 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 iterationsusing 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:
5
Time Complexity: O(N * M2)
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 codeint main(){ // Number of iterationsint N = 4;// Number of tasksint M = 4;// Cost matrixvector<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 iterationsN = 4# Number of tasksM = 4# Cost matrixcost_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 iterationslet N = 4;// Number of taskslet M = 4;// Cost matrixlet 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
5
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
