动态规划 - 2016网易杭研面试题

有一个边长为n的立方体,内部的每一个小立方体内有一个数字。如果取了当前这个小立方体，则小立方体的：

上下相邻两层将会消失;

前后相邻两列将会消失;

左右相邻两个将会消失;

找出一种取法，使得取到的数的sum最大，输出sum。

现场面第三轮遇到了这一题，想了五分钟没想出来，面试官就不让想了TAT

回来想出了解法，当时现场面试还是有点紧张了，只想出了二维的做法.

对于这题，关键的地方在于找对DP的顺序：点-->线-->面

首先考虑规则3（左右相邻两个将会消失），可以将3维dp压缩到2维，且不会破环约束条件；

再来考虑规则2（前后相邻两列将会消失），可以将2维dp压缩到1维，且不会破环约束条件；

最后对1维的数组在进行一次dp，结果即为答案.

由于需要遍历三维空间，故时间复杂度为O(N^3)。