一道动规的题，求求大家帮帮我！！！急需这几天出答案

是这样的，面试了一个教授，到了最后一步他出了道他算法题给我要求用动态规划做，我没做出来他现在让我回家做，做了好多天了我还是没头绪，但是再拖下去我肯定会丢了这个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，而且要求必须用动态规划做。

谢谢大家了！

PHD offer 还是 MS ？

没接触过动态规划的，帮顶顶。。。。。

虾米出江湖 发表于 2013-12-27 13:10
PHD offer 还是 MS ？

港科MPHIL，算是MS吧，不过也几乎都是在research

虾米出江湖 发表于 2013-12-27 13:11
没接触过动态规划的，帮顶顶。。。。。

谢谢你！

LZ你这题目表述不清啊。我有2个疑问。
1）最多几个plan是指这些plan都要同时存在并且互不相交是吧？你的说法会让人觉得是每个plan互不影响。
2）一个plan是只有一个track可以转弯吗？还是任何一个track都可以转？

wjl2525 发表于 2013-12-27 13:48
LZ你这题目表述不清啊。我有2个疑问。
1）最多几个plan是指这些plan都要同时存在并且互不相交是吧？你的说 ...

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

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

懂了。我也来想想怎么做。

wjl2525 发表于 2013-12-27 14:12
懂了。我也来想想怎么做。

多谢多谢！我之前想过不交叉的话可以参照最长上升子序列之类的，但又有挺多不一样的地方

动态规划确实不太会。。。灰常抱歉。。。。但是无限支持楼主~