Amazon一道Onsite 题

cgdong2012 · 2014-12-13 06:34:50

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

一个朋友取A家面试遇到的一个题，我到现在也没太

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

有谁知道具体解法吗？
拜谢了

jacgraphy · 2014-12-13 10:55:29

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

cgdong2012 · 2014-12-13 11:10:10

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

cgdong2012 · 2014-12-13 09:18:06

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

Adeath · 2014-12-13 07:05:06

我记得以前好像有一道类似的只能取首尾的问最后取得的数的和
这题是用递归做每次取数前计算取哪个数可以获得更大的和因为两人都会采用相同的策略实际上数组确定后两人的取数就确定了
优化用DP

MCwong · 2014-12-13 08:34:52

数组可见么, 两人都是同一种策略吗？感觉可以用Minimax tree再加上alpha-beta pruning优化.

cgdong2012 · 2014-12-13 09:18:40

MCwong 发表于 2014-12-13 08:34
数组可见么, 两人都是同一种策略吗？感觉可以用Minimax tree再加上alpha-beta pruning优化.

数组可见的，经过楼上提醒，是每次只能取首尾的数字。

Adeath · 2014-12-13 09:41:32

cgdong2012 发表于 2014-12-13 09:18
对，是只能取首尾的，不能用贪婪算法，因为对面的可能取到更大的数。第一想法用递归没错，但是我还是 ...

http://www.1point3acres.com/bbs/ ... kbox%26sortid%3D311
找到这个帖子了第二轮的题
我的想法跟这个lz的是一样的

cgdong2012 · 2014-12-13 09:43:54

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

jlin705 · 2014-12-13 10:05:20

我面google onsite考得这道题。。。。

cgdong2012 · 2014-12-13 10:36:45

jlin705 发表于 2014-12-13 10:05
我面google onsite考得这道题。。。。

我了个去，这个题这么高频，你最后解法是哪个？面试官满意否？

pyemma · 2014-12-13 10:45:55

只能取首位的话是不是就是coin in a line那道题啊？是这个么？http://leetcode.com/2011/02/coins-in-line.html