测试数据

问题描述

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

1. 上下相邻两层将会消失;
2. 前后相邻两列将会消失;
3. 左右相邻两个将会消失;

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

问题分析

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

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

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

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

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

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

时间复杂度

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

代码

#include 
     
      using namespace std;class Solution{public:   int getMax(vector
      
       
        
          > > &cube)   {       int n=cube.size();       vector
         
          
            > dp2(n,vector
           
            (n,0)); vector
            
              tp(n); // 3D zip to 2D for(int i=0;i
             

dp1(n,0); // 2D zip to answer for(int i=0;i