python - 找到矩阵中元素的最小和，使得在加法过程中列应该是连续的

Question

我实际上想从矩阵中获得最小总和，以便从矩阵中选择的元素使得列应该是连续的，并且如果选择了任何新行，则元素不应该从旧行中选择。例如，如果添加arr[0][0] + arr[1][1] + arr[0][2] as arr[0][2]不应该存在，因为我们在第二次添加矩阵时更改了行。例子-：

1 9 1
2 0 3 
1 7 3

所以上面arr[0][0] + arr[1][1] +arr[0][1] =1 + 0 + 1 = 2给出了最小总和但这是不被接受的总和应该被arr[0][0] + arr[1][1] + arr[2][2] = 1 +0 + 3 = 4接受。无论选择所有行元素还是应该选择每列中的元素并且没有元素应该是同一列或前一列只有连续的列添加是接受的
输入-：

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

我的代码

# 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)

标签： pythonarraysdynamic-programmingmemoization