Google二跪

hlckl123456 发表于 2018-9-8 06:12
一维数组就可以了吧，j是用来干嘛的

嗯，这个地方写的有问题。因为每次只从头开始拿

贡献一个dp写法，思路仿照两边取牌

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

被选择后的数字的左右两边算连续的数字吗？

比如1，2，3，4，5，6的2，3被拿走后，1和4算不算连续数字可以同时被选择呢？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

贴一个DP的解法，如有问题还请指正。

1. #include <iostream>
   
2. 
   
3. bool solution(vector<int>nums)
   
4. {   
   
5.     int N = nums.size();
   
6.     vector<int>sum(N+1);
   
7.     sum[N] = 0;
   
8.     for (int i=N-1; i>=0; i--)
   
9.         sum[i] = sum[i+1]+nums[i];
   
10.    
    
11.     vector<int>dp(N+1,0);
    
12.     dp[N-1]=sum[N-1];
    
13.     dp[N-2]=max(sum[N-2],nums[N-2]);
    
14.    
    
15.     for (int i=N-3; i>=0; i--)
    
16.     {
    
17.         int scoreA = nums[i]+sum[i+1]-dp[i+1];
    
18.         int scoreB = nums[i]+nums[i+1]+sum[i+2]-dp[i+2];
    
19.         int scoreC = nums[i]+nums[i+1]+nums[i+2]+sum[i+3]-dp[i+3];
    
20.         dp[i] = max(scoreA,scoreB);
    
21.         dp[i] = max(dp[i],scoreC);
    
22.     }
    
23.     return dp[0]>=sum[0]-dp[0];        
    
24. }
    
25. 
    
26. int main()
    
27. {
    
28.     vector<int>nums({1,2,-3,8});   
    
29.     cout<<solution(nums)<<endl;
    
30. }

复制代码

rexue70 发表于 2018-9-8 05:17
写了个recursive版本的

[mw_shl_code=java,true]

感谢分享。我理解这个返回的应该是先手的最优解吧。返回的时候是不是应该比较一下这个opt 和 sum - opt 然后返回较大的那个结果？

Lynn_Wang 发表于 2018-9-26 13:20
感谢分享。我理解这个返回的应该是先手的最优解吧。返回的时候是不是应该比较一下这个opt 和 sum - opt  ...

题目说了“自己先开始，问最多能获得的分数是多少”，没办法sum - opt吧，这样是后手了吧？我理解的就是求先手最优解

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rexue70 发表于 2018-9-27 08:39
题目说了“自己先开始，问最多能获得的分数是多少”，没办法sum - opt吧，这样是后手了吧？我理解的就是 ...

哦哦 没仔细看题目 理解错了~

wisdompeak2 发表于 2018-9-21 16:56
贴一个DP的解法，如有问题还请指正。
[mw_shl_code=cpp,true]#include

哥们这个题目要求返回的是最大值而不是bool。。。