2016网易杭研笔试题A
Problem's Link
----------------------------------------------------------------------------
Mean:
有一个边长为n的立方体,内部的每一个小立方体内有一个数字。如果取了当前这个小立方体，则小立方体的：
1.上下相邻两层将会消失;
2.前后相邻两列将会消失;
3.左右相邻两个将会消失;
找出一种取法，使得取到的数的sum最大，输出sum。
analyse:
现场面试时挂在这题上了，想了五分钟没想出来，面试官就不让想了TAT
回来想了一下，是个简单题，当时现场面试还是有点紧张了，只想出了二维的做法.
对于这题，关键的地方在于找对DP的顺序：点-->线-->面
首先考虑规则3（左右相邻两个将会消失），可以将3维dp压缩到2维，且不会破环约束条件；
再来考虑规则2（前后相邻两列将会消失），可以将2维dp压缩到1维，且不会破环约束条件；
最后对1维的数组在进行一次dp，结果即为答案.
看着挺复杂，想到了就是个大水题.
Time complexity: O(N^3)
view code
));
;;;);
;;);
;)
)));
;;;;
;;;);
;;);
;)
)));
;;;;
*/