动态规划 - 2016网易杭研面试题-阿里云开发者社区

开发者社区> 云计算> 正文

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

简介: mean 有一个边长为n的立方体,内部的每一个小立方体内有一个数字。如果取了当前这个小立方体,则小立方体的: 上下相邻两层将会消失; 前后相邻两列将会消失; 左右相邻两个将会消失; 找出一种取法,使得取到的数的sum最大,输出sum。

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)。

code

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
   int getMax(vector<vector<vector<int> > > &cube)
   {
       int n=cube.size();
       vector<vector<int> > dp2(n,vector<int>(n,0));
       vector<int> tp(n);
       // 3D zip to 2D
       for(int i=0;i<n;++i)
       {
           for(int j=0;j<n;++j)
           {
               for(int k=0;k<n;++k)
               {
                   tp[k]=cube[i][k][j];// be careful
               }
               dp2[i][j]=zipToPoint(tp);
           }
       }

       vector<int> dp1(n,0);
       // 2D zip to answer
       for(int i=0;i<n;++i)
       {
           for(int j=0;j<n;++j)
               tp[j]=dp2[i][j];
           dp1[i]=zipToPoint(tp);
       }
       return zipToPoint(dp1);
   }

   int zipToPoint(vector<int> & nums)
   {
       int n=nums.size();
       vector<int> dp(n,0);
       dp[0]=nums[0];
       for(int i=1;i<n;++i)
       {
           if(i==1)
               dp[i]=max(dp[0],nums[1]);
           else
               dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
       }
       return dp[n-1];
   }
};


int main()
{
   int T,n;
   scanf("%d",&T);
   while(T--)
   {
       scanf("%d",&n);
       vector<vector<vector<int> > > cube(n,vector<vector<int> >(n,vector<int>(n,0)));
       for(int i=0;i<n;++i)
       {
           for(int j=0;j<n;++j)
           {
               for(int k=0;k<n;++k)
                   scanf("%d",&cube[i][j][k]);
           }
       }
       Solution solution;
       int ans=solution.getMax(cube);
       printf("%d\n",ans);
   }
   return 0;
}

test data

/*
-----------------------
1
3
1 2 3
4 5 6
7 8 9

10 11 12
13 14 15
16 17 18

19 20 21
22 23 24
25 26 27
-----------------------
112

*/

 

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章