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)