Minimize total cost without repeating same task in two consecutive iterations | C ++ implementation of the above approach ; Function to return the minimum cost for N iterations ; Construct the dp table ; 1 st row of dp table will be equal to the 1 st of cost matrix ; Iterate through all the rows ; To iterate through the columns of current row ; Initialize val as infinity ; To iterate through the columns of previous row ; Fill the dp matrix ; Returning the minimum value ; Driver code ; Number of iterations ; Number of tasks ; Cost matrix
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findCost ( vector < vector < int > > cost_mat , int N , int M ) { vector < vector < int > > dp ( N , vector < int > ( M , 0 ) ) ; for ( int i = 0 ; i < M ; i ++ ) dp [ 0 ] [ i ] = cost_mat [ 0 ] [ i ] ; for ( int row = 1 ; row < N ; row ++ ) { for ( int curr_col = 0 ; curr_col < M ; curr_col ++ ) { int val = 999999999 ; for ( int prev_col = 0 ; prev_col < M ; prev_col ++ ) { if ( curr_col != prev_col ) val = min ( val , dp [ row - 1 ] [ prev_col ] ) ; } dp [ row ] [ curr_col ] = val + cost_mat [ row ] [ curr_col ] ; } } int ans = INT_MAX ; for ( int i = 0 ; i < M ; i ++ ) ans = min ( ans , dp [ N - 1 ] [ i ] ) ; return ans ; } int main ( ) { int N = 4 ; int M = 4 ; 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 ; }