s********u
发帖数: 1109 | 1 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归函数。
恕我愚笨，如果用dp，我不知道怎么解决。但用memoization（top-down）就可以很方
便解决，从上往下递归时顺便存进table。
当然，这里实际的原因是，memoization本身就属于广义的dp，所以“当满足最优子结
构、subproblem overlap的时候可以用dp”还是成立的。
那么问题就来了，如何区分，memoization和狭义dp（循环，bottom-up）呢。
=============================================================
我自己是这么总结的：
解决从起点到终点的问题，也就是通过解决subproblem到达胜利条件的问题，
1.如果起点和终点已知，那么可以用dp，
比如n的阶乘，Fibonacci的非递归解法，爬楼梯问题，其实也是dp。
然后记录一个int set的所有子集，或者string的所有permutation（起点、终点都只有
一个就是数组的头尾）
还有就是比如leetcode的unique path，虽然看上去是dfs，但实际起点、终点都是固定
的，都只有一个。
或者word break问题，虽然看起来很花哨，但是起点和终点还是只有一个。
这些都可以用dp。
如果需要记录路径，用prev[n]数组来记录。
2.如果起点或终点未知，或者说非常多（ 比如超过O(1) )，那么就用递归（通常是
backtracking
），比如boggle game，比如二叉树判断一个节点是否在里面，比如组一个最高的box的
堆（cc150 9.10）。如果有overlap的情况，再引入memoization。
如果需要记录路径，用一个vector inplace操作即可
其实我相信这种情况还是可以用dp解的，不过问题瞬间复杂许多，感觉远远超出了面试
的需要。特别是不少情况用memoization，大体上可以妥协一下。
//当然，这里没有包含BFS这种方式。事实是，我们没有考虑贪心算法，比如dijkstra
算法（BFS时期特殊形式），比如longest increasing sub-sequence的贪心解法。至于
贪心算法和dp到底什么关系，我还在研究。。。 |
s*****r
发帖数: 108 | 2 这个标题就很奇怪 看完后果然没几句正确
不过楼主精神还是挺好的 可惜经验太少
还有贪心和 DP 的关系 这应该是算法课就教的
建议楼主多看下书有个好基础 别根据做的几个题就总结 |
b*******e
发帖数: 123 | 3 你可以详细说说么。
【在 s*****r 的大作中提到】
: 这个标题就很奇怪 看完后果然没几句正确
: 不过楼主精神还是挺好的 可惜经验太少
: 还有贪心和 DP 的关系 这应该是算法课就教的
: 建议楼主多看下书有个好基础 别根据做的几个题就总结
|
s********u
发帖数: 1109 | 4 我本来就是想“功利”地从解决题目的角度出发，不过理论方面也翻了不少资料。如果
有原则性错误的话，方便指正一下么？
【在 s*****r 的大作中提到】
: 这个标题就很奇怪 看完后果然没几句正确
: 不过楼主精神还是挺好的 可惜经验太少
: 还有贪心和 DP 的关系 这应该是算法课就教的
: 建议楼主多看下书有个好基础 别根据做的几个题就总结
|
b*******e
发帖数: 123 | 5 感觉dp和recursion都是解决recursive equation 的。如果你方便把recursive call
的输入变成有限n-维区间上的整数，就可以建dp table。不方便就用recursion +
memoization。
【在 s********u 的大作中提到】
: 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
: 前言：
: 我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
: 个条件个人感觉不太实用。
: 1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
: 所以这个原则应该是“适合用dp”，而不是“可以用dp”
: 另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
: 是有重复的，但是
: subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
: 2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
|
p*****2
发帖数: 21240 | |
s********u
发帖数: 1109 | 7 是的。一般dp能解决的，recursion（可以用memoization辅助）都能解决，只是一个
bottom-up，一个top-down。我想观察的就是什么样的问题用dp“方便”解决。
目前的结论是，如果这个问题的起点和终点都是“收敛”的（就算中间过程有多么发散
），那么通常方便用dp解决。例如unique path ii或者word break。
如果有一端是发散的（相对），那么用dp就比较难解决了。例如DFS（path sum），八
皇后。
【在 b*******e 的大作中提到】
: 感觉dp和recursion都是解决recursive equation 的。如果你方便把recursive call
: 的输入变成有限n-维区间上的整数，就可以建dp table。不方便就用recursion +
: memoization。
|
b*******e
发帖数: 123 | 8 FP可不可以自动memoization? 加个关键字啥的，compiler自动根据input type 加个 n
-tuple -> return value type 的
dictionary。 好象不是很难的功能。
【在 p*****2 的大作中提到】
: FP里只有递归，没有循环
|
p*****2
发帖数: 21240 | 9
能举个例子吗？没太看明白。
【在 b*******e 的大作中提到】
: FP可不可以自动memoization? 加个关键字啥的，compiler自动根据input type 加个 n
: -tuple -> return value type 的
: dictionary。 好象不是很难的功能。
|
s********u
发帖数: 1109 | 10 如果compiler如此智能的话，可以随便用递归而不用考虑效率了吧。。反正overlap会
自动解决
n
【在 b*******e 的大作中提到】
: FP可不可以自动memoization? 加个关键字啥的，compiler自动根据input type 加个 n
: -tuple -> return value type 的
: dictionary。 好象不是很难的功能。
|
|
|
p*****2
发帖数: 21240 | 11
n
看明白了。这个倒是个好问题。
【在 b*******e 的大作中提到】
: FP可不可以自动memoization? 加个关键字啥的，compiler自动根据input type 加个 n
: -tuple -> return value type 的
: dictionary。 好象不是很难的功能。
|
b*******e
发帖数: 123 | 12 例如，
def memo Fibo(n):
if(n<3):
return 1;
else:
return Fibo(n-1) + Fibo(n-2);
因为有memo keyword, compiler 会自动加个dictionary(int,int),compiler 出来的
psedo-code 是
di = {}
def Fibox(n):
if n in di:
return di[n];
else:
di[n] = Fibo(n)
return di[n]
当然这个是简单例子，如果有很多input parameter的话，好像会简洁些。 |
p*****2
发帖数: 21240 | 13
嗯。理论上真的可行。我甚至觉得应该有这个东西，不过刚才搜了一下没搜到。不知道
有没有哪个FP的语言已经实现了，如果这样的话DP就太简单了。
【在 b*******e 的大作中提到】
: 例如，
: def memo Fibo(n):
: if(n<3):
: return 1;
: else:
: return Fibo(n-1) + Fibo(n-2);
: 因为有memo keyword, compiler 会自动加个dictionary(int,int),compiler 出来的
: psedo-code 是
: di = {}
: def Fibox(n):
|
b*******e
发帖数: 123 | |
p*****2
发帖数: 21240 | 15
这个用clojure来做的话，还真的不难。
【在 b*******e 的大作中提到】
: 是哦。您给编一个？ :P
|
b*******e
发帖数: 123 | |
p*****2
发帖数: 21240 | 17
写了一个简单的。
(def memo (atom {}))
(defmacro defn-memo [name params & body]
`(defn ~name ~params
(let [key# (concat '(~name) ~params)]
(when-not (contains? @memo key#)
(swap! memo assoc key# (do ~@body)))
(@memo key#))))
(defn-memo add [x y]
(println "aaa")
(+ x y))
(println (add 1 2))
(println (add 2 3))
(println (add 1 2))
【在 b*******e 的大作中提到】
: 网上没有,是不是其实实际中没人用DP。。。
|
b*******e
发帖数: 123 | 18 受教了。c++ 或者 java 应该也可以吧。关键字是没戏了，functor? |
n********n
发帖数: 529 | |
l*n
发帖数: 529 | 20 不明白什么叫自动，计算机应该没办法猜出来程序应该怎么记录子问题结果吧，起码
base case是要人指定才行。如果单纯指后者，可以看看javascript: the good parts
44页的memoization一节，应该是很典型的fp用法。
【在 p*****2 的大作中提到】
:
: 写了一个简单的。
: (def memo (atom {}))
: (defmacro defn-memo [name params & body]
: `(defn ~name ~params
: (let [key# (concat '(~name) ~params)]
: (when-not (contains? @memo key#)
: (swap! memo assoc key# (do ~@body)))
: (@memo key#))))
: (defn-memo add [x y]
|
|
|
p*****2
发帖数: 21240 | 21
parts
FP里面都是纯函数，没有side effect。也就是说同样的输入，输出一定是相同的。这
样的话，确实没有必要重复计算了。编译器可以优化纪录结果，针对相同的输入只计算
一次。javascript到不算是FP语言，function是first citizen, 但是有side effect.
【在 l*n 的大作中提到】
: 不明白什么叫自动，计算机应该没办法猜出来程序应该怎么记录子问题结果吧，起码
: base case是要人指定才行。如果单纯指后者，可以看看javascript: the good parts
: 44页的memoization一节，应该是很典型的fp用法。
|
b*******e
发帖数: 123 | 22 能说的再通俗点么？
我怎么觉得比较输入相同这个不是很容易阿，要是输入是个curried function, 化简后
一样算么？
你的意思是不是对于一个call path,compiler应该记忆所有多次call的function的
return value, 因为反正是immutable，算一次就不会变了。
【在 p*****2 的大作中提到】
:
: parts
: FP里面都是纯函数，没有side effect。也就是说同样的输入，输出一定是相同的。这
: 样的话，确实没有必要重复计算了。编译器可以优化纪录结果，针对相同的输入只计算
: 一次。javascript到不算是FP语言，function是first citizen, 但是有side effect.
|
d******l
发帖数: 98 | 23 建议楼主看看 CLRS那本书。。
其实DP 与 Divide-and-Conqur 很接近，就是没有重复的subproblem的，就属于Divide
-and-Conqur范围了，DC的subproblem是disjoint的，就是分类讨论的那种，，然后加
上 recursion。。
【在 s********u 的大作中提到】
: 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
: 前言：
: 我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
: 个条件个人感觉不太实用。
: 1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
: 所以这个原则应该是“适合用dp”，而不是“可以用dp”
: 另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
: 是有重复的，但是
: subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
: 2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
|
d******l
发帖数: 98 | 24 算法 其实常见的就三种： DC（Divide-and-Conquer）， DP 和 greedy 。。 |
s********u
发帖数: 1109 | 25 嗯，在理论上我是这么总结的：
**Divide and conquer :** 将问题分成几个部分，每一部分问题互相不重叠，假定每
个部分都可以得到解决进行递归调用，合并每一部分的结果。例如Merge Sort,Quick
Sort。
**Dynamic Programming**：对于具备最优子结构以及子问题重叠特性的问题，尽可能
不重复计算每个subproblem，将计算结果存储下来，以确定后驱问题的结果。与贪心算
法的区别是，在计算后驱问题时，可能会reconsider前驱问题的解，从而改变全局path
。
**Greedy Algorithm** : 当前问题的最优解只取决于前驱问题的最优解，即局部最
优解推广至全局最优解。如Dijkstra算法。
**Backtracking**： 一种暴力（穷举）的深度优先搜索法，直至检索到节点空间的尽
头。Tree或Graph的DFS，是backtracking的special case。
但实际上很多问题就算满足dp的条件，用dp却非常繁琐，比如8皇后问题，或path sum
问题。是可以用dp做，但实际上没必要。用backtracking+剪枝就可以做到很不错的效
率（因为错误的枝都被剪了，所以走过的路径跟dp实际是一样的）。
Divide
【在 d******l 的大作中提到】
: 建议楼主看看 CLRS那本书。。
: 其实DP 与 Divide-and-Conqur 很接近，就是没有重复的subproblem的，就属于Divide
: -and-Conqur范围了，DC的subproblem是disjoint的，就是分类讨论的那种，，然后加
: 上 recursion。。
|
p*****2
发帖数: 21240 | 26
这就是lisp的强大之处了。code就是data。curried function也是data。很容易做key。
就是这个意思。
【在 b*******e 的大作中提到】
: 能说的再通俗点么？
: 我怎么觉得比较输入相同这个不是很容易阿，要是输入是个curried function, 化简后
: 一样算么？
: 你的意思是不是对于一个call path,compiler应该记忆所有多次call的function的
: return value, 因为反正是immutable，算一次就不会变了。
|
q***s
发帖数: 487 | 27 mark
【在 s********u 的大作中提到】
: 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
: 前言：
: 我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
: 个条件个人感觉不太实用。
: 1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
: 所以这个原则应该是“适合用dp”，而不是“可以用dp”
: 另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
: 是有重复的，但是
: subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
: 2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
|
s******y
发帖数: 416 | 28 DP和递归不是一个层面的概念，不能比较适用范围…
【在 s********u 的大作中提到】
: 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
: 前言：
: 我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
: 个条件个人感觉不太实用。
: 1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
: 所以这个原则应该是“适合用dp”，而不是“可以用dp”
: 另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
: 是有重复的，但是
: subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
: 2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
|
p*****2
发帖数: 21240 | 29
key。
昨天发现原来clojure本身就支持memorize呀。这样的话，用clojure做dp不是太爽了，
cache都不用自己搞了。
dfs＋cache dp王道呀。
【在 p*****2 的大作中提到】
:
: 这就是lisp的强大之处了。code就是data。curried function也是data。很容易做key。
: 就是这个意思。
|
y*******g
发帖数: 6599 | 30 和上次你总结的那个什么hashmap用bst差不多 无从指正。
【在 s********u 的大作中提到】
: 我本来就是想“功利”地从解决题目的角度出发，不过理论方面也翻了不少资料。如果
: 有原则性错误的话，方便指正一下么？
|
