Maximize count of indices with same element by pairing rows from given Matrices | Function to find the maximum defined score ; If all students are assigned ; Check if row is not paired yet ; Check for all indexes ; If values at current indexes are same increase curSum ; Further recursive call ; Store the ans for current mask and return ; Utility function to find the maximum defined score ; Create a mask with all set bits 1 -> row is not paired yet 0 -> row is already paired ; Initialise dp array with - 1 ; Driver Code
def maxScoreSum ( a , b , row , mask , dp ) : NEW_LINE INDENT if ( row >= len ( a ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ mask ] != - 1 ) : NEW_LINE INDENT return dp [ mask ] NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT if ( mask & ( 1 << i ) ) : NEW_LINE INDENT newMask = mask ^ ( 1 << i ) NEW_LINE curSum = 0 NEW_LINE for j in range ( len ( a [ i ] ) ) : NEW_LINE INDENT if ( a [ row ] [ j ] == b [ i ] [ j ] ) : NEW_LINE INDENT curSum += 1 NEW_LINE DEDENT DEDENT ans = max ( ans , curSum + maxScoreSum ( a , b , row + 1 , newMask , dp ) ) NEW_LINE DEDENT DEDENT dp [ mask ] = ans NEW_LINE return dp [ mask ] NEW_LINE DEDENT def maxScoreSumUtil ( a , b , N , M ) : NEW_LINE INDENT row = 0 NEW_LINE mask = pow ( 2 , M ) - 1 NEW_LINE dp = [ - 1 ] * ( mask + 1 ) NEW_LINE return maxScoreSum ( a , b , row , mask , dp ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE M = 3 NEW_LINE a = [ [ 1 , 1 , 0 ] , [ 1 , 0 , 1 ] , [ 0 , 0 , 1 ] ] NEW_LINE b = [ [ 1 , 0 , 0 ] , [ 0 , 0 , 1 ] , [ 1 , 1 , 0 ] ] NEW_LINE print ( maxScoreSumUtil ( a , b , N , M ) ) NEW_LINE DEDENT