问如何将三维数组描述为表格？

EN

既然您在动态编程的上下文中提到了2d和3d数组，那么让我提供一个二维问题的示例，它很好地利用了基于动态编程的方法，然后将其扩展到第三维。也许这将有助于将其可视化。

让我们考虑这个问题:给出一个矩阵A，其中n行，m列填充整数，您从第一行中选择的单元格开始。每转一圈，你要么直接移动到你所在的单元格的正下方，要么移动到它的一个邻居那里。更正式地说，您可以从单元格(i, j)前进到(i+1, j)、(i+1,j-1)、(i+1,j+1)之一。到达最后一行后，将遍历的所有单元格的数字相加。通过这种方式，您可以获得的最大金额是多少？

动态规划方法如下:引入与A相同维度的第二个矩阵B，并将B[i][j]定义为“如果您遵循问题的条件并到达单元格(i, j)，则达到的最大可能和”。换句话说，如果您的旅程从第一行的任何位置开始，以单元格(i, j)结束，那么最大和可能是多少？

这个定义有一个相对简单的递归关系：

B[0][j] = A[0][j]
B[i][j] = max(B[i-1][j], B[i-1][j-1], B[i-1][j+1]) + A[i][j] for i>0

或者在英语中:我们通过(i-1,j)，(i-1, j-1)，(i-1, j+1)中的一个得到(i, j)，因此我们对这些路径中最好的路径求和，并在(i, j)中给它增加值。因此，B就是您引用的DP表。

现在让我们从三维角度考虑一个类似的问题:您所在的建筑物具有K层，并且每层都是一个填充了整数的n x m矩阵。让我们将floor上的矩阵称为x A_x，例如，3楼的单元格(i, j)中的数字是A_3[i][j]。你从一楼的任何一个单元格开始，每转一圈，你就可以跳到更高的一层，要么直接跳到上面的单元格，要么跳到它的8个邻居中的一个：

(i-1, j-1)  (i-1,  j )   (i-1, j+1)
( i,  j-1)  (  i,  j )   ( i,  j+1)
(i+1, j-1)  (i+1,  j )   (i+1, j+1)

同样，当您到达顶层时，您将完成操作，并尝试最大化您遍历的所有单元格的总和。

让我们介绍一个3d矩阵B[k][i][j]，它将包含您从第一层开始并当前到达floor k，(i, j)的情况下可能获得的最大和。递归关系为：

B[1][i][j] = A_1[i][j]
B[k][i][j] = max(A_(k-1)[i-1][j-1], A_(k-1)[i-1][j], ..., A_(k-1)[i+1][j+1]) + A_k[i][j] for k>0

公式中的那些...代表了所有的8个方向(现在我真的很后悔我说了8个方向，如果这会让一切变得更难理解的话)。所以，用简单的英语，我们再次说类似于前面的话:我们从(i, j) on floor k-1下面的8个单元格中的一个来到floor k-1上的单元格(i, j)，所以让我们选择最好的路径。

B[k][i][j]是用于保存DP条目的3维矩阵，它本质上是堆叠在一起的k表。