一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1280|回复: 22
收起左侧

[算法题] 一道动规的题,求求大家帮帮我!!!急需这几天出答案

[复制链接] |试试Instant~ |关注本帖
peikexin9 发表于 2013-12-27 13:01:10 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
是这样的,面试了一个教授,到了最后一步他出了道他算法题给我要求用动态规划做,我没做出来他现在让我回家做,做了好多天了我还是没头绪,但是再拖下去我肯定会丢了这个offer的,所以恳请大家帮帮我,越快越好

上下是两条边是side A和side B, 分别有相对应的9个点,两个side之间有四个track。现在定义了plan:从一个点到另一个点,然后中间可以选择在任意一个track转两次弯,也可以不转弯。(比如plan 1,那条红色的,就转了两次到下面某个点,又比如plan 2, 就没转,到了下面的某个点,再比如plan 3或plan 4, 他转了两次回到了同一个side的某个点)。某一条线可以是一个plan,当然几条线组合在一起又是一个新的plan,比如图中所画的两条线,既可以分别是plan 1和plan 2,也可以合在一起叫做一个新的plan, 比如就叫plan 5吧。但是,多条线组成一个plan有一个条件,就是这多条线不能相交,比如图中plan 1和plan 3那两条线合在一起可以构成一个新的plan,但是plan 1和plan 4就不行,因为他们这样算是相交,当然更别提那些直接交叉的两条线了。
现在就是想问,这样的话最多能有多少个plan,而且要求必须用动态规划做。
dp problem.jpg 谢谢大家了!
虾米出江湖 发表于 2013-12-27 13:10:30 | 显示全部楼层
PHD offer 还是 MS ?
回复 支持 反对

使用道具 举报

虾米出江湖 发表于 2013-12-27 13:11:15 | 显示全部楼层
没接触过动态规划的,帮顶顶。。。。。
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-27 13:12:39 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-27 13:13:04 | 显示全部楼层
虾米出江湖 发表于 2013-12-27 13:11
没接触过动态规划的,帮顶顶。。。。。

谢谢你!
回复 支持 反对

使用道具 举报

wjl2525 发表于 2013-12-27 13:48:45 | 显示全部楼层
LZ你这题目表述不清啊。我有2个疑问。
1)最多几个plan是指这些plan都要同时存在并且互不相交是吧?你的说法会让人觉得是每个plan互不影响。
2)一个plan是只有一个track可以转弯吗?还是任何一个track都可以转?
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-27 14:07:30 | 显示全部楼层
wjl2525 发表于 2013-12-27 13:48
LZ你这题目表述不清啊。我有2个疑问。
1)最多几个plan是指这些plan都要同时存在并且互不相交是吧?你的说 ...

对不起啊,可能我表述不清,因为我收到的题目也是口述的,没有文字原题
其实plan就是一条线或者多条线,也就是说任意一条线可以是一个plan,任意多条线合在一起也可以是一个plan,所谓不相交,是指多条线合在一起组成一个plan的时候,不能相交,所以
1)最多几个plan是问:一共有多少个不一样的plan,当然这些plan之间相交都是有可能的,只要不一样就行
2)一个plan只能在任意一个track转两次次弯(从垂直变成水平方向,然后再再变成垂直方向),在某个track转过了,就再也不能转了,所以说一条线可以有两种选择:在某个track转,或者完全不转,走直线下去
谢谢你愿意来看看题目!
回复 支持 反对

使用道具 举报

wjl2525 发表于 2013-12-27 14:12:27 | 显示全部楼层
peikexin9 发表于 2013-12-27 14:07
对不起啊,可能我表述不清,因为我收到的题目也是口述的,没有文字原题
其实plan就是一条线或者多条线, ...

懂了。我也来想想怎么做。
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-27 14:14:25 | 显示全部楼层
wjl2525 发表于 2013-12-27 14:12
懂了。我也来想想怎么做。

多谢多谢!我之前想过不交叉的话可以参照最长上升子序列之类的,但又有挺多不一样的地方
回复 支持 反对

使用道具 举报

Honeybear 发表于 2013-12-27 22:52:47 | 显示全部楼层
动态规划确实不太会。。。灰常抱歉。。。。但是无限支持楼主~
回复 支持 反对

使用道具 举报

zerowing444 发表于 2013-12-27 23:21:40 | 显示全部楼层
我刚注册,看看能不能发帖,能发就说点思路
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-27 23:24:00 | 显示全部楼层
zerowing444 发表于 2013-12-27 23:21
我刚注册,看看能不能发帖,能发就说点思路

就在这回复呢?
回复 支持 反对

使用道具 举报

zerowing444 发表于 2013-12-27 23:50:44 | 显示全部楼层
你这样想试试:从左往右一列一列考虑,在第一列,你可以什么都不做,可以竖着连下来,也可以在第1到4个track时候拐到下一列。这样一共6种情况,其中4种拐的情况会影响到下一列的考虑,你可以把从上一列拐过来的line想象成“必须处理的接口”,每个接口有三种处理方法:拐上去,拐下去,或连到下一列。这就是大概的思路了,但还有好多细节需要考虑,比如说有从上一列来的track3的接口,那你这一列如果要开一个新line的话就不能直接从A连到B了,只能有两种情况:新线路在track1拐或track2拐;再比如你从上一列收到两个接口,那么位置靠上那个接口在这一列的处理方法只能是向上拐或连到下一列,相对位置靠下的只能向下拐或连到下一列,如果三个或更多那么位于中间的就只能连到下一列。总之有挺多情况需要考虑。以上假设所有line只能从A开始。

我的拙见,思路不是很清晰,但希望能帮你扩展一下思路。
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-28 00:15:52 | 显示全部楼层
zerowing444 发表于 2013-12-27 23:50
你这样想试试:从左往右一列一列考虑,在第一列,你可以什么都不做,可以竖着连下来,也可以在第1到4个trac ...

谢谢你!不过也可以从B开始吧?
回复 支持 反对

使用道具 举报

zerowing444 发表于 2013-12-28 00:21:28 | 显示全部楼层
peikexin9 发表于 2013-12-28 00:15
谢谢你!不过也可以从B开始吧?

这就不知道了,你得问教授。如果可以从B开始的话就多几种情况,不过差不多。
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-28 00:23:40 | 显示全部楼层
zerowing444 发表于 2013-12-28 00:21
这就不知道了,你得问教授。如果可以从B开始的话就多几种情况,不过差不多。

是可以从B开始的,总之就是一个点和另一个点相连,就能够成一条线,可能直接划下去,也可能经过某个track转两次到两一个点
回复 支持 反对

使用道具 举报

1guangnian 发表于 2013-12-28 05:32:06 | 显示全部楼层
说下我的一点点思路吧,可能会对楼主有帮助,dp[i][j][mask]表示最后一个单条线的plan,一端在sideA的i处,另一端在sideB的j处,然后已经在mask表示的track集合转过弯,然后楼主可以枚举这个(i, j)可以转移到哪些新的i',j',并且转弯处不会与mask集合有冲突,然后就是细节问题了
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-28 14:16:18 | 显示全部楼层
1guangnian 发表于 2013-12-28 05:32
说下我的一点点思路吧,可能会对楼主有帮助,dp[j][mask]表示最后一个单条线的plan,一端在sideA的i处,另一 ...

恩,我现在就是这么想的,主要是想想dp在最右那条单线该记录些什么信息就够了
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2013-12-28 14:16:28 | 显示全部楼层
1guangnian 发表于 2013-12-28 05:32
说下我的一点点思路吧,可能会对楼主有帮助,dp[j][mask]表示最后一个单条线的plan,一端在sideA的i处,另一 ...

谢谢你!
回复 支持 反对

使用道具 举报

 楼主| peikexin9 发表于 2014-1-5 11:29:45 | 显示全部楼层
感谢各位!这道题在大家的帮助下我做出来了,用了一下状态压缩,想通了确实代码就几行,谢谢大家热心帮助!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 07:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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