python - 最小垂直切片和

Question

我想输入一个矩阵大小 N x N 并切割一个切片，使每个元素都在它上面的元素的正下方、左下方或右下方。而成本是切片中所有元素的总和。我该如何编写程序来执行此操作？

例如。矩阵作为列表的列表给出

[[1,2,3],
 [4,5,6],
 [7,8,9]]

它有以下切片:

(1,4,7), (1,4,8), (1,5,7), (1,5,8), (1,5,9), 
(2,4,7), (2,4,8), (2,5,7), (2,5,8), (2,5,9), (2,6,8), (2,6,9), 
(3,5,7), (3,5,8), (3,5,9), (3,6,8), (3,6,9)

那么权重最低的切片是 (1,4,7)，其总和为 12。

Answer 1

正如 vivek 提到的，您可以使用动态程序解决此问题:

创建一个与输入矩阵大小相同的成本表。成本矩阵的每个元素都存储以该元素结束的最小切片的成本。如果您还将前面的切片元素存储在此成本表中，则还可以在最后提取实际的切片(而不仅仅是其成本)。

您可以很容易地初始化成本表。只需将输入矩阵的第一行复制到表格中。然后，我们将逐行填充表格的其余部分。设C 为成本矩阵，M 为输入矩阵。然后:

//Initialize cost table
for col = 0 to N - 1
    C(0, col) = M(0, col)
//Run dynamic program
for row = 1 to N - 1
    for col = 0 to N - 1
        //take the minimum of the three possible predecessors:
        //make sure that the entries exist (i.e., take care of the edges, not shown here)
        C(row, col) = M(row, col) 
                       + min(C(row - 1, col - 1)), C(row - 1, col), C(row - 1, col + 1))

在此之后，您只需要在 C 的最后一行中找到最小值，这将为您提供最小切片的成本。要获得实际的切片，请沿着您在循环期间设置的前导指针走(伪代码片段中未显示)。