一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

码农求职神器Triplebyte
不用海投
内推多家公司面试

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 608|回复: 6
收起左侧

[动态规划] 只以面试为目的,395 lintcode Coins in a line II这种题目是不是最好直接放弃?

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
whodatj | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (20)
 
 
9% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 whodatj 于 2019-8-25 08:45 编辑

Description
There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.
Could you please decide the first player will win or lose?

If the first player wins, return true, otherwise return false.


Example 1:

Input: [1, 2, 2]
Output: true
Explanation: The first player takes 2 coins.
Example 2:

Input: [1, 2, 4]
Output: false
Explanation: Whether the first player takes 1 coin or 2, the second player will gain more value.

理解答案有困难,不是很想浪费时间在这里。。什么公司会考这种DP题。
BTW请问LEETCODE上有没有类似的题目

上一篇:64Minimum Path Sum 能帮忙看看用Dijkstra不可以吗?
下一篇:排列组合题的框架思路和题目总结
我的人缘0
cai_lw 2019-8-25 10:02:07 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   96% (707)
 
 
3% (29)    👎
博弈题并不罕见,直接在leetcode上搜Game可以搜到不少,解法基本是数学证明或DP
DP的目标函数是每个状态下先手是否必胜(对于只有胜负没有分数的博弈)或先手可以得到的最大收益(对于有分数的零和博弈)
状态转移方程是:当前状态的函数值等于走一步能达到的状态的DP函数值中的最小值(因为走一步能达到的状态是对手先手,我们要尽量让对手少得分)
回复

使用道具 举报

我的人缘0
337845818 2019-8-25 10:06:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   72% (352)
 
 
27% (136)    👎
不会做也看不懂答案就别研究了, 何必难为自己?
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (97)
 
 
3% (3)    👎
g面经出现过类似题
回复

使用道具 举报

我的人缘0
advincenting 2019-8-25 10:45:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
有 输入脑筋急转弯题型 
回复

使用道具 举报

我的人缘0
gundamkeroro 2019-8-25 11:28:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (380)
 
 
6% (28)    👎
一般来说除了几家有题库而且题库比较小的公司 比如dropbox, LinkedIn, Facebook这种之外的题  其他的题就是练练手而已 不过这道题没啥难理解的吧 博弈形dp考的还是挺多的
回复

使用道具 举报

我的人缘0
 楼主| whodatj 2019-8-25 13:46:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (20)
 
 
9% (2)    👎
已明白,主要是刷心态有点崩。冷静一下 看两遍就理解了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-9-21 07:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表