最简单的倒立方法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

最简单的倒立方法

最简单的倒立方法# Joke - 肚皮舞运动

n*r2011-09-02 07:09

1 楼

原帖在这里：
http://www.mitbbs.com/article_t/JobHunting/31996705.html
题目是：
“2. Given two strings that one string contains the other string, while
the other string could be split into any set of substrings. Please find
the minimum split time. Example: "apple pie is deicious" contains
"applepie"'s substring set "apple" and "pie", so the minimum split time
is 1”
看回帖有人说是DP + recursive, 百思不得其解
请教一下大家～

r*e2011-09-02 07:09

2 楼

最简单的倒立方法 j.jpg

a*m2011-09-02 07:09

3 楼

dp+recursive? 这种说法有点奇怪。也许说的是recursive+memo. 都差不多。不过dp好像定义也没有那么严格。
感觉是dp问题。每个分隔点可以完全分隔或者连接两边不同数目的字符加上两遍被隔
开的两块的结果。

e*t2011-09-02 07:09

4 楼

鸡大无头。

【在 r*********e 的大作中提到】

: 最简单的倒立方法 j.jpg

z*e2011-09-02 07:09

5 楼

这种问切成2边的题目,有的好像只讨论其中一边.
比如在CLRS上,rod cutting问题,和这个这个形似.

a*e2011-09-02 07:09

6 楼

好大的龟头！

t*72011-09-02 07:09

7 楼

也算是DP+RECUR
其实RECUR可解了,只是开销太大,要O(2^n)
如果加一个中间数据结构,动态记录的话,只要O(n^2)

f*d2011-09-02 07:09

8 楼

hao

n*r2011-09-02 07:09

9 楼

恩，好像是这样, thanks!

好像定义也没有那么严格。

【在 a********m 的大作中提到】

: dp+recursive? 这种说法有点奇怪。也许说的是recursive+memo. 都差不多。不过dp好像定义也没有那么严格。
: 感觉是dp问题。每个分隔点可以完全分隔或者连接两边不同数目的字符加上两遍被隔
: 开的两块的结果。

a*a2011-09-02 07:09

10 楼

。。。。哈哈
我刚开始还没看明白图片
看了这句才明白

【在 a*******e 的大作中提到】

: 好大的龟头！

n*r2011-09-02 07:09

11 楼

谢谢啦～
能不能解释下这两个复杂度呢？
实在是想不明白。

【在 t*********7 的大作中提到】

: 也算是DP+RECUR
: 其实RECUR可解了,只是开销太大,要O(2^n)
: 如果加一个中间数据结构,动态记录的话,只要O(n^2)

c*h2011-09-02 07:09

12 楼

猛一看还真像

g*s2011-09-02 07:09

13 楼

yes. i agree with you.
It is a just normal DP question. You can implement it with recusive function
, or just for-loop.
1) build v(x,y),1<=x<=y<=n; v(x,y)=true if sub string bwn [x,y] is valid O
(N^2)
2) f(n) = min { (f(i) + 1 if v(i+1,n)=true} ; --if no such i, f(n)=infinite
O(N^2)
return f(N)

好像定义也没有那么严格。

【在 a********m 的大作中提到】

v*m2011-09-02 07:09

14 楼

笑了

【在 r*********e 的大作中提到】

: 最简单的倒立方法 j.jpg

n*w2011-09-02 07:09

15 楼

recursive的意思是指dp可以写成递归形式吧。
更具体的说，是dp + recursive + backtrace。比ls的那个O(n^2)应该还要好一点。
做法是
1 先把valid的单词存成一个tries
2 从头往尾扫，找到所有valid的单词。比如applepie，假设a和apple都是valid。
3 a和apple都试一试。a的话，subproblem变成了split pplepie。apple的话，
subproblem变成了split pie。
用到了tries来剪枝，同时递归的写dp，面试的时候时间上充裕点。

【在 t*********7 的大作中提到】

: 也算是DP+RECUR
: 其实RECUR可解了,只是开销太大,要O(2^n)
: 如果加一个中间数据结构,动态记录的话,只要O(n^2)