n****r
发帖数: 471 | 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, 百思不得其解
请教一下大家～ | a********m
发帖数: 15480 | 2 dp+recursive? 这种说法有点奇怪。也许说的是recursive+memo. 都差不多。不过dp好像定义也没有那么严格。
感觉是dp问题。每个分隔点可以完全分隔或者连接两边不同数目的字符加上两遍被隔
开的两块的结果。 | z***e
发帖数: 209 | 3 这种问切成2边的题目,有的好像只讨论其中一边.
比如在CLRS上,rod cutting问题,和这个这个形似. | t*********7
发帖数: 255 | 4 也算是DP+RECUR
其实RECUR可解了,只是开销太大,要O(2^n)
如果加一个中间数据结构,动态记录的话,只要O(n^2) | n****r
发帖数: 471 | 5 恩，好像是这样, thanks!
好像定义也没有那么严格。
【在 a********m 的大作中提到】
: dp+recursive? 这种说法有点奇怪。也许说的是recursive+memo. 都差不多。不过dp好像定义也没有那么严格。
: 感觉是dp问题。每个分隔点可以完全分隔或者连接两边不同数目的字符加上两遍被隔
: 开的两块的结果。
| n****r
发帖数: 471 | 6 谢谢啦～
能不能解释下这两个复杂度呢？
实在是想不明白。
【在 t*********7 的大作中提到】
: 也算是DP+RECUR
: 其实RECUR可解了,只是开销太大,要O(2^n)
: 如果加一个中间数据结构,动态记录的话,只要O(n^2)
| g***s
发帖数: 3811 | 7 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 的大作中提到】
: dp+recursive? 这种说法有点奇怪。也许说的是recursive+memo. 都差不多。不过dp好像定义也没有那么严格。
: 感觉是dp问题。每个分隔点可以完全分隔或者连接两边不同数目的字符加上两遍被隔
: 开的两块的结果。
| n*******w
发帖数: 687 | 8 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)
|
|
