一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

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

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 816|回复: 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)   👎
全局: 👍   94% (800)
 
 
5% (46)    👎
博弈题并不罕见,直接在leetcode上搜Game可以搜到不少,解法基本是数学证明或DP
DP的目标函数是每个状态下先手是否必胜(对于只有胜负没有分数的博弈)或先手可以得到的最大收益(对于有分数的零和博弈)
状态转移方程是:当前状态的函数值等于走一步能达到的状态的DP函数值中的最小值(因为走一步能达到的状态是对手先手,我们要尽量让对手少得分)

评分

参与人数 2大米 +3 收起 理由
LeonChen + 2 给你点个赞!
kyzgz + 1 赞一个

查看全部评分

回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-20 07:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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