s********u
发帖数: 1109 | 1 我看了careercup的书，上面说DP就是做recursion的时候把已经算过的结果cache一下
，可以在subproblems overlap的时候提高效率。
但我看好多人提到dp的时候，比如leetcode的unique path一题，往往是bottom-up，也
就是把subproblems的值存到数组里，然后用iteration来计算出problem的结果。
到底哪个概念更通用一点？如果面试官要求用dp，指的是哪一种？
因为第一种解释做起来很简单，就加个hashtable就行，要改成第二种解释的话还要把
recursion改写成iteration，就复杂多了。 |
z****e
发帖数: 54598 | |
s********u
发帖数: 1109 | 3 我的意思是那就不叫DP了吧？比如最简单的fibnacci
我用三个临时变量循环计算出f(n)，这也叫DP?
有点搞糊涂了，因为careercup书上说的dp，似乎就是等同于大家所说的memoization...
【在 z****e 的大作中提到】
: 可以用循环实现啊
: 为什么一定要用递归
|
z****e
发帖数: 54598 | 4 当然算咯
而且一般写dp都是用循环实现的
而不是递归，递归效率偏低
...
【在 s********u 的大作中提到】
: 我的意思是那就不叫DP了吧？比如最简单的fibnacci
: 我用三个临时变量循环计算出f(n)，这也叫DP?
: 有点搞糊涂了，因为careercup书上说的dp，似乎就是等同于大家所说的memoization...
|
s********u
发帖数: 1109 | 5 哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
比如这个题：
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
的答案。
如果要求用dp的话，递归还是要比循环好写很多吧。。
【在 z****e 的大作中提到】
: 当然算咯
: 而且一般写dp都是用循环实现的
: 而不是递归，递归效率偏低
:
: ...
|
z****e
发帖数: 54598 | 6 dp就是数学归纳法，从前面已知的结果推导出当前的结果
循环一般比递归节省时间和空间
【在 s********u 的大作中提到】
: 哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
: 比如这个题：
: 给一个bool IsWord(string)的API, 判断能否把一个string分割成单词， 并给出所有
: 的答案。
: 如果要求用dp的话，递归还是要比循环好写很多吧。。
|
g**G
发帖数: 767 | 7 DP一般你会写出最优的子问题的递归方程对吧，其实就是递归
只不过一般DP是自底向上的，Recursion+cache是自顶向下的，写的顺序不一样
DP效率高，但理解起来可能比较困难
Recursion+cache的话，想起来比较顺溜，但是其实虽然中间结果cache了，但重复的
function call还是太多了，比dp效率低 |
s*****h
发帖数: 155 | 8 你说的cache的这种属于自顶向下的DP，应该算是递归，需要一个global var
CLRS专门有一章讲DP的，有背包，编辑距离以及折棍子几个例子，讲得很清楚
【在 s********u 的大作中提到】
: 我看了careercup的书，上面说DP就是做recursion的时候把已经算过的结果cache一下
: ，可以在subproblems overlap的时候提高效率。
: 但我看好多人提到dp的时候，比如leetcode的unique path一题，往往是bottom-up，也
: 就是把subproblems的值存到数组里，然后用iteration来计算出problem的结果。
: 到底哪个概念更通用一点？如果面试官要求用dp，指的是哪一种？
: 因为第一种解释做起来很简单，就加个hashtable就行，要改成第二种解释的话还要把
: recursion改写成iteration，就复杂多了。
|
j******i
发帖数: 244 | 9 DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
过节省了stack空间。 |
s*****r
发帖数: 108 | 10 是递推不是 DP
【在 z****e 的大作中提到】
: dp就是数学归纳法，从前面已知的结果推导出当前的结果
: 循环一般比递归节省时间和空间
|
|
|
F*****e
发帖数: 331 | 11
"而将DAG做toposort以后确定了各个顶点的前后关系，从后往前iterate，"
DAG是什么？你说的toposort是用来建finite machine的吗？
【在 j******i 的大作中提到】
: DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
: 立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
: 想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
: 用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
: 点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
: 过节省了stack空间。
|
c********p
发帖数: 1969 | |
s******c
发帖数: 1920 | 13 DP 可以用递归来实现 (算出来一个子问题的解以后存下来 下次直接查表).
也可以不用递归直接用查表填表的方式实现.
我上的算法课上, 老师实际上先用递归来演示DP的精髓.
【在 s********u 的大作中提到】
: 我看了careercup的书，上面说DP就是做recursion的时候把已经算过的结果cache一下
: ，可以在subproblems overlap的时候提高效率。
: 但我看好多人提到dp的时候，比如leetcode的unique path一题，往往是bottom-up，也
: 就是把subproblems的值存到数组里，然后用iteration来计算出problem的结果。
: 到底哪个概念更通用一点？如果面试官要求用dp，指的是哪一种？
: 因为第一种解释做起来很简单，就加个hashtable就行，要改成第二种解释的话还要把
: recursion改写成iteration，就复杂多了。
|
s*****r
发帖数: 108 | 14 DAG 是有向无环图
有了 toposort 才知道应该怎样从前往后递推
否则的话得写记忆话搜索
所以进行 DP 通常这两种实现；知道了自底向上的顺序用递推
不知道又不想拓扑排序后再推就用递归 用这种形式感觉不怎么动脑子把转移方程放那
开头判断个边界就好了 好像显得没有递推实现高端
上面的回复大多不准确或者错误的
直到 jianglai 说到了本质 引入了拓扑排序好像蒙了一下 但把模型转化为 DAG 是
必要的 只是我们刚开始碰到的 DP 大都划分阶段显然 知道了推的顺序 其实在一些树
或图上的 DP 不容易递推实现 因为要么得先拓扑排序从边界开始向后推 要么用了巧妙
的实现方式那是非常值得一读的程序
【在 F*****e 的大作中提到】
:
: "而将DAG做toposort以后确定了各个顶点的前后关系，从后往前iterate，"
: DAG是什么？你说的toposort是用来建finite machine的吗？
|
s***e
发帖数: 403 | 15 DP是剑法
递归是内功
相同的剑法可以用不同的内功驱动
就是这个意思。 |
f********4
发帖数: 988 | 16
就是为了翻出这段话。。mark
【在 j******i 的大作中提到】
: DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
: 立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
: 想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
: 用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
: 点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
: 过节省了stack空间。
|
r*******h
发帖数: 315 | 17 最直观的递归往往会重复计算一个子问题，DP主要目的是解决子问题的重复解带来的指
数级开销，但是并不意味着DP不能和递归共存。
【在 s********u 的大作中提到】
: 我看了careercup的书，上面说DP就是做recursion的时候把已经算过的结果cache一下
: ，可以在subproblems overlap的时候提高效率。
: 但我看好多人提到dp的时候，比如leetcode的unique path一题，往往是bottom-up，也
: 就是把subproblems的值存到数组里，然后用iteration来计算出problem的结果。
: 到底哪个概念更通用一点？如果面试官要求用dp，指的是哪一种？
: 因为第一种解释做起来很简单，就加个hashtable就行，要改成第二种解释的话还要把
: recursion改写成iteration，就复杂多了。
|
