香港西贡街头扫狗 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

香港西贡街头扫狗 (转载)

香港西贡街头扫狗 (转载)# pets - 心有所宠

s*u2012-09-19 07:09

1 楼

我看了careercup的书，上面说DP就是做recursion的时候把已经算过的结果cache一下
，可以在subproblems overlap的时候提高效率。
但我看好多人提到dp的时候，比如leetcode的unique path一题，往往是bottom-up，也
就是把subproblems的值存到数组里，然后用iteration来计算出problem的结果。
到底哪个概念更通用一点？如果面试官要求用dp，指的是哪一种？
因为第一种解释做起来很简单，就加个hashtable就行，要改成第二种解释的话还要把
recursion改写成iteration，就复杂多了。

x*r2012-09-19 07:09

2 楼

一件是Burberry原价无折895刀，一件事Vera Wang原价1995，不过打半价998刀，还要
天杀的10%的税，真是要出血了，版上的jjmm们说那件好。我倾向打半价的。

a*s2012-09-19 07:09

3 楼

【以下文字转载自 Animals 讨论区】
发信人: ironhand (hard), 信区: Animals
标题: 香港西贡街头扫狗
发信站: BBS 未名空间站 (Wed Sep 19 00:00:53 2012, 美东)

z*e2012-09-19 07:09

4 楼

可以用循环实现啊
为什么一定要用递归

m*i2012-09-19 07:09

5 楼

Y*y2012-09-19 07:09

6 楼

第一张眼好大！

s*u2012-09-19 07:09

7 楼

我的意思是那就不叫DP了吧？比如最简单的fibnacci
我用三个临时变量循环计算出f(n)，这也叫DP?
有点搞糊涂了，因为careercup书上说的dp，似乎就是等同于大家所说的memoization...

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

: 可以用循环实现啊
: 为什么一定要用递归

p*m2012-09-19 07:09

8 楼

2

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

: 一件是Burberry原价无折895刀，一件事Vera Wang原价1995，不过打半价998刀，还要
: 天杀的10%的税，真是要出血了，版上的jjmm们说那件好。我倾向打半价的。

z*e2012-09-19 07:09

9 楼

当然算咯
而且一般写dp都是用循环实现的
而不是递归，递归效率偏低

...

【在 s********u 的大作中提到】

: 我的意思是那就不叫DP了吧？比如最简单的fibnacci
: 我用三个临时变量循环计算出f(n)，这也叫DP?
: 有点搞糊涂了，因为careercup书上说的dp，似乎就是等同于大家所说的memoization...

y*s2012-09-19 07:09

10 楼

贴个照片看看你mm身材适合长款短款？脸型发型肩宽适合大领小领立领塌领？肤色是粉
底黄底？。。第一个一般般，第二个显老，当然如果是美女穿啥都好看！

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

: 一件是Burberry原价无折895刀，一件事Vera Wang原价1995，不过打半价998刀，还要
: 天杀的10%的税，真是要出血了，版上的jjmm们说那件好。我倾向打半价的。

s*u2012-09-19 07:09

11 楼

哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
比如这个题：
给一个bool IsWord(string)的API, 判断能否把一个string分割成单词，并给出所有
的答案。
如果要求用dp的话，递归还是要比循环好写很多吧。。

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

: 当然算咯
: 而且一般写dp都是用循环实现的
: 而不是递归，递归效率偏低
:
: ...

w*t2012-09-19 07:09

12 楼

give her a classic burberry trench coat
http://us.burberry.com/product/index.jsp?productId=4031130&cp=2067810 $995

z*e2012-09-19 07:09

13 楼

dp就是数学归纳法，从前面已知的结果推导出当前的结果
循环一般比递归节省时间和空间

【在 s********u 的大作中提到】

: 哦我大致明白了，就是通过space cost来换取time cost的，就是dp？
: 比如这个题：
: 给一个bool IsWord(string)的API, 判断能否把一个string分割成单词，并给出所有
: 的答案。
: 如果要求用dp的话，递归还是要比循环好写很多吧。。

h*y2012-09-19 07:09

14 楼

两个都不咋的，不值得花那个钱。。。

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

: 一件是Burberry原价无折895刀，一件事Vera Wang原价1995，不过打半价998刀，还要
: 天杀的10%的税，真是要出血了，版上的jjmm们说那件好。我倾向打半价的。

g*G2012-09-19 07:09

15 楼

DP一般你会写出最优的子问题的递归方程对吧，其实就是递归
只不过一般DP是自底向上的，Recursion+cache是自顶向下的，写的顺序不一样
DP效率高，但理解起来可能比较困难
Recursion+cache的话，想起来比较顺溜，但是其实虽然中间结果cache了，但重复的
function call还是太多了，比dp效率低

h*y2012-09-19 07:09

16 楼

yes, 要买就买他家经典的！

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

: give her a classic burberry trench coat
: http://us.burberry.com/product/index.jsp?productId=4031130&cp=2067810 $995

s*h2012-09-19 07:09

17 楼

你说的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，就复杂多了。

I*e2012-09-19 07:09

18 楼

re啊re啊

【在 h********y 的大作中提到】

: 两个都不咋的，不值得花那个钱。。。

j*i2012-09-19 07:09

19 楼

DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
过节省了stack空间。

f*g2012-09-19 07:09

20 楼

if you mm is yong, both of them not really fit :)

s*r2012-09-19 07:09

21 楼

是递推不是 DP

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

: dp就是数学归纳法，从前面已知的结果推导出当前的结果
: 循环一般比递归节省时间和空间

e*62012-09-19 07:09

22 楼

颜色绝对选2,1的颜色像铁锈红，丑死了
款型：要看MM是不是模特身材了，高挑身材选2，
一般身高的选1

F*e2012-09-19 07:09

23 楼

"而将DAG做toposort以后确定了各个顶点的前后关系，从后往前iterate，"
DAG是什么？你说的toposort是用来建finite machine的吗？

【在 j******i 的大作中提到】

: DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
: 立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
: 想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
: 用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
: 点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
: 过节省了stack空间。

x*r2012-09-19 07:09

24 楼

我就市不喜欢他家的双排扣子，亚洲人穿不出效果阿。

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

: give her a classic burberry trench coat
: http://us.burberry.com/product/index.jsp?productId=4031130&cp=2067810 $995

c*p2012-09-19 07:09

25 楼

来mark一下，我其实也总晕这个。

h*e2012-09-19 07:09

26 楼

这件burberry似乎一般，但颜色是好看的
vera wang我觉得很一般，对不起它的价钱

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

: 一件是Burberry原价无折895刀，一件事Vera Wang原价1995，不过打半价998刀，还要
: 天杀的10%的税，真是要出血了，版上的jjmm们说那件好。我倾向打半价的。

s*c2012-09-19 07:09

27 楼

DP 可以用递归来实现 (算出来一个子问题的解以后存下来下次直接查表).
也可以不用递归直接用查表填表的方式实现.
我上的算法课上, 老师实际上先用递归来演示DP的精髓.

【在 s********u 的大作中提到】

x*r2012-09-19 07:09

28 楼

恩，burberry这件看不出是burberry的，除了一边肩上那一块搭下来的地方，但是颜色
真的不错，vera wang放大了能看到料子很有质感，穿起来应该很舒服，据说是丝+羊毛
的，真纠结阿。

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

: 这件burberry似乎一般，但颜色是好看的
: vera wang我觉得很一般，对不起它的价钱

s*r2012-09-19 07:09

29 楼

DAG 是有向无环图
有了 toposort 才知道应该怎样从前往后递推
否则的话得写记忆话搜索
所以进行 DP 通常这两种实现；知道了自底向上的顺序用递推
不知道又不想拓扑排序后再推就用递归用这种形式感觉不怎么动脑子把转移方程放那
开头判断个边界就好了好像显得没有递推实现高端
上面的回复大多不准确或者错误的
直到 jianglai 说到了本质引入了拓扑排序好像蒙了一下但把模型转化为 DAG 是
必要的只是我们刚开始碰到的 DP 大都划分阶段显然知道了推的顺序其实在一些树
或图上的 DP 不容易递推实现因为要么得先拓扑排序从边界开始向后推要么用了巧妙
的实现方式那是非常值得一读的程序

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

:
: "而将DAG做toposort以后确定了各个顶点的前后关系，从后往前iterate，"
: DAG是什么？你说的toposort是用来建finite machine的吗？