z*********8
发帖数: 2070 | 1 resume talk
算法:
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
的答案。
没答好， 用了recursion没想到DP.
问： 怎么知道某个问题可以用DP做？ |
w******j
发帖数: 185 | |
z*********8
发帖数: 2070 | 3 嗯我也看到了。。。事情太多准备不够， 脑子也不够活络了 |
w******j
发帖数: 185 | |
l*n
发帖数: 529 | 5 有subproblem overlap的递归都是dp。
【在 z*********8 的大作中提到】
: resume talk
: 算法:
: 给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
: 的答案。
: 没答好， 用了recursion没想到DP.
: 问： 怎么知道某个问题可以用DP做？
|
c********p
发帖数: 1969 | |
f*******b
发帖数: 520 | 7
对，一看就知道是上DP
【在 l*n 的大作中提到】
: 有subproblem overlap的递归都是dp。
|
p*****2
发帖数: 21240 | 8 LZ解的不错，这个帖子太误导了，这题一看就是DFS。 |
l*n
发帖数: 529 | 9 计算是否能split直接dfs & backtrack是不错。不过需要输出所有组合的话，还是需要
memoization的。比如feelink，可以是fee+link也可以是feel+ink，所以dp还是要的。
【在 p*****2 的大作中提到】
: LZ解的不错，这个帖子太误导了，这题一看就是DFS。
|
p*****2
发帖数: 21240 | 10
感觉你说反了。
【在 l*n 的大作中提到】
: 计算是否能split直接dfs & backtrack是不错。不过需要输出所有组合的话，还是需要
: memoization的。比如feelink，可以是fee+link也可以是feel+ink，所以dp还是要的。
|
|
|
s********u
发帖数: 1109 | 11 感觉比唯一解的那个题目复杂好多。因为是要输出所有组合，如果说dp的话，也就是说
要建立一个 map< string, vector >，然后再把这个vector里的string都遍历
一遍，和prefix的单词组合起来，组成新的vector？想想就头大。。。 |
m*****k
发帖数: 731 | |
s********u
发帖数: 1109 | 13 不需要吧？递归的返回值是一个 vector就可以了吧？
只是DP应该能降低time cost，因为的确是有重复的subproblems，只是感觉也会增加许
多 space cost。
【在 l*n 的大作中提到】
: 计算是否能split直接dfs & backtrack是不错。不过需要输出所有组合的话，还是需要
: memoization的。比如feelink，可以是fee+link也可以是feel+ink，所以dp还是要的。
|
p*****2
发帖数: 21240 | 14 (def dict #{"i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream",
"icecream",
"man", "go", "mango"})
(def input "ilikesamsung")
(defn dfs [str, start, curr, list]
(if (= curr (count str))
(when (= start (count str))
(println (reverse list)))
(let [next (inc curr) sub (subs str start next)]
(when (contains? dict sub)
(dfs input next next (cons sub list)))
(dfs input start next list))
))
(dfs input 0 0 ()) |
A***o
发帖数: 358 | 15 output sensitive，用动态规划改变不了指数复杂度的本质，recursion就好了 |
f*******w
发帖数: 1243 | 16 这种要列出所有答案的，明显recursion啊
DP没用 |
f*****t
发帖数: 13 | 17 用DP存的都是答案，输出的每一条path都是答案，而直接recursion大部分path可能都
不是答案。
不过像楼上说的，output sensitive，用动态规划改变不了指数复杂度的本质，
recursion就好了。理论上复杂度是一样的。
写起来的话，肯定是直接dfs简单。
面试官的要求是关键。上次半海不是说写了个dp的，结果面试官不懂dp。
【在 f*******w 的大作中提到】
: 这种要列出所有答案的，明显recursion啊
: DP没用
|
s********u
发帖数: 1109 | 18 C++写了一个，如果不用DP的话，把这个map去掉即可，试了一两个字符串似乎没问题。
vector wordBreak( string s, map< string, vector >& cache){
vector vs;
vector suffixSet;
string tmp;
if( s.size() == 0 ){
vs.push_back(s);
return vs;
}
if(cache.count(s) > 0)
return cache[s];
string prefix, suffix;
for(int i = 1; i <= s.size(); i++){
prefix = s.substr(0,i);
if( isWord(prefix) ){
suffix = s.substr(i);
suffixSet = wordBreak(suffix,cache);
for(vector::iterator it = suffixSet.begin(); it !=
suffixSet.end(); it++){
tmp = prefix + ' ' + (*it);
vs.push_back(tmp);
}
}
}
cache[s] = vs;
return vs;
} |
s********u
发帖数: 1109 | 19 不过似乎很多人说的dp跟我理解的不是一回事。好像很多人说到DP，实际上是用非递归
的方法？我理解的dp就是careercup书上写的，把已经算过的结果存起来。。汗 |
