find the minimum sum of element in a matrix such that column should be consecutive during addition

Viewed 354

I would actually want to get minimum sum from the matrix so that element chosen from the matrix such that column should be consecutive and element should not choose from old row if any new row is chosen. for example if addition is arr[0][0] + arr[1][1] + arr[0][2] as arr[0][2] should not be there as we change the row in second addition of matrix. example-:

1 9 1
2 0 3 
1 7 3

so in above arr[0][0] + arr[1][1] +arr[0][1] =1 + 0 + 1 = 2 gives min sum but this is not accepted sum should be arr[0][0] + arr[1][1] + arr[2][2] = 1 +0 + 3 = 4 is accepted.no matter all row element is chosen or not only element from each column should be chosen and no element should be same column or the previous column only consecutive column addition is accepted
input -:

3 3
1 2 2 
2 1 2
3 2 1 

output -: arr[0][0] + arr[1][1] + arr[2][2] = 3

input -:
3 3
1 2 2 
2 5 2
3 2 2

output -: arr[0][0] + arr[0][1] + arr[0][2] = 5

input -:
3 3
1 2 2 
2 5 2
1 1 1

output -: arr[2][0] +arr[2][1] + arr[2][2]


the above test case runs fine but my code fails for some test cases

input -:
3 3
1 2 3 
1 2 3
0 3 1

expected output -: 4 
my output -: 3

4 2
2 2 2 2
1 2 3 4

expected output -: 8
my output -: 3

My code

# cook your dish here

import math
def mincost(matrix,initial_row,initial_col,prevcol,col,row):
    if initial_row == row or initial_col == col:
        return 0
  
    dp = [[math.inf for x in range(col+1)] for y in range(row)]
    if dp[initial_row][prevcol+1] != math.inf:
        return dp[initial_row][prevcol+1]
    res = math.inf
    for i in range(row):
        if initial_col != prevcol:
            val = matrix[i][initial_col] + mincost(matrix,i,initial_col+1,initial_col,row,col)
            res = min(res,val)
        dp[i][prevcol+1] = res  
    return res

# main fuction    
col,row = input( ).split( )
row = int(row)
col = int(col)
matrix=[ ]
for i in range(row):
    row_list=[int(x) for x in input( ).split( )]
    matrix.append(row_list)

#sending perivious column as -1 to backtrack the element should not from previous column 
result = mincost(matrix,0,0,-1,col,row)
print(result)
0 Answers
Related