Re: 上厕所如何压水花？ (转载) - 未名空间MITBBS历史存档

Re: 上厕所如何压水花？ (转载)# Joke - 肚皮舞运动

p*22012-01-05 08:01

1 楼

不断看到有新人学习DP，想谈谈我的感受。
我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
没有用cache。
开始学习DP是在careercup 150那本书上。下面是一些感受。
1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出
F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的，可能就得多练习
了，培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同，一个
是推公式，一个是找recursion的办法。而DP的关键是推公式，如果从recursion出发的
话，很多题可能做不出来。
做DP题需要注意两点：
1. 能用iteration就不要用recursion。这也证明了careercup上的定义有局限性了。
2. DP是用空间换时间。所以DP题做熟了，应该考虑怎样优化空间了。能用常数空间就
不要用O(n), 能用O(n)就不要用O(n^2). (我觉得这也是Vissa的霸气所在。Vissa面F
的时候说过“这么简单的DP题，我从来都是用常数空间”）。
最后就是多做题才能培养思路。一般面试应该不会有很难的DP题，多练习一下有了思路
，再能写出iteration和空间优化的解法，并且能保证少bug的话，应该面试就差不多了
。

C*g2012-01-05 08:01

2 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: elvinGG (♡ ♡ ♡), 信区: WaterWorld
标题: Re: 上厕所如何压水花？
发信站: BBS 未名空间站 (Thu Jan 5 00:58:47 2012, 美东)
还有个办法，用手接住然后慢慢放进去

f*22012-01-05 08:01

3 楼

学习了

w*z2012-01-05 08:01

4 楼

您工作还没着落呢？是不是挑花眼了？

p*22012-01-05 08:01

5 楼

没有呀。我去年连DP都不会，面试全fail掉了。

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

: 您工作还没着落呢？是不是挑花眼了？

H*y2012-01-05 08:01

6 楼

thanks

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

d*y2012-01-05 08:01

7 楼

Cracking code interview那本书上错的很多，
而且有几个地方说的很有误导，包括面试时写代码的注意事项，
那本书应该最后看，（看完introduction to algorithms和其他经典书以后）

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

g*y2012-01-05 08:01

8 楼

赞！进来学习一下。

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

i*e2012-01-05 08:01

9 楼

特地进来帮你顶一下。
赞学习精神.

w*x2012-01-05 08:01

10 楼

说的不错.我想补充一下:
Iteration能完全代替recursion的只有tail recursion或用栈.
题目做多了很容易感觉出哪题需要用到DP,很多地方不一定要从公式推出.
DP不明显的问题上来说, 需要仔细观察你的解法中是不是有 "重复计算", 把"重复计算
"用数据结构存储最优子结构就可以了.
有的DP可以继续化简空间复杂度, 比如LCS可以把空间复杂度O(n^2)减少到O(n),因为第
n步的DP只和前一步(第n-1步)的最优子结果有关, 从公式上也可以看出F(n)只和F(n-1
)有关.

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

d*u2012-01-05 08:01

11 楼

赞总结，bless find dream job！

p*22012-01-05 08:01

12 楼

不断看到有新人学习DP，想谈谈我的感受。
我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
没有用cache。
开始学习DP是在careercup 150那本书上。下面是一些感受。
1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出
F(n)来。当然这也是最难的。发现很多难题还是很难想到这个公式的，可能就得多练习
了，培养思路。这个定义跟careercup上的不一样的地方主要是思考的方式不同，一个
是推公式，一个是找recursion的办法。而DP的关键是推公式，如果从recursion出发的
话，很多题可能做不出来。
做DP题需要注意两点：
1. 能用iteration就不要用recursion。这也证明了careercup上的定义有局限性了。
2. DP是用空间换时间。所以DP题做熟了，应该考虑怎样优化空间了。能用常数空间就
不要用O(n), 能用O(n)就不要用O(n^2). (我觉得这也是Vissa的霸气所在。Vissa面F
的时候说过“这么简单的DP题，我从来都是用常数空间”）。
最后就是多做题才能培养思路。一般面试应该不会有很难的DP题，多练习一下有了思路
，再能写出iteration和空间优化的解法，并且能保证少bug的话，应该面试就差不多了
。

f*22012-01-05 08:01

13 楼

学习了

w*z2012-01-05 08:01

14 楼

您工作还没着落呢？是不是挑花眼了？

p*22012-01-05 08:01

15 楼

没有呀。我去年连DP都不会，面试全fail掉了。

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

: 您工作还没着落呢？是不是挑花眼了？

H*y2012-01-05 08:01

16 楼

thanks

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

d*y2012-01-05 08:01

17 楼

Cracking code interview那本书上错的很多，
而且有几个地方说的很有误导，包括面试时写代码的注意事项，
那本书应该最后看，（看完introduction to algorithms和其他经典书以后）

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

g*y2012-01-05 08:01

18 楼

赞！进来学习一下。

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

i*e2012-01-05 08:01

19 楼

特地进来帮你顶一下。
赞学习精神.

w*x2012-01-05 08:01

20 楼

说的不错.我想补充一下:
Iteration能完全代替recursion的只有tail recursion或用栈.
题目做多了很容易感觉出哪题需要用到DP,很多地方不一定要从公式推出.
DP不明显的问题上来说, 需要仔细观察你的解法中是不是有 "重复计算", 把"重复计算
"用数据结构存储最优子结构就可以了.
有的DP可以继续化简空间复杂度, 比如LCS可以把空间复杂度O(n^2)减少到O(n),因为第
n步的DP只和前一步(第n-1步)的最优子结果有关, 从公式上也可以看出F(n)只和F(n-1
)有关.

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

d*u2012-01-05 08:01

21 楼

赞总结，bless find dream job！

l*a2012-01-05 08:01

22 楼

牛

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

l*b2012-01-05 08:01

23 楼

CLRS上面是不是有一个专门的recursion+cache的叫法？memoization？那个大牛给定义
一下。DP还是好难想出来啊。

d*x2012-01-05 08:01

24 楼

CLRS上不是说过了关键就是最优子结构嘛。。。

【在 l**b 的大作中提到】

: CLRS上面是不是有一个专门的recursion+cache的叫法？memoization？那个大牛给定义
: 一下。DP还是好难想出来啊。

p*22012-01-05 08:01

25 楼

才注意这是去年3月份写的。看来这几个月都荒废了。没啥进步呀。

t*a2012-01-05 08:01

26 楼

楼上的都是大牛，抛砖引玉，介绍介绍偷懒的办法
clojure上面的DP可以用memoize recusion function来做，懒汉专用工具 :)
但是这样的recusion还是有可能stack overflow，怎么办呢？
懒汉的办法就是再构造一个lazy sequence从小到大call过去，就保证了recusion不太
会发生了
这样的话，如果memoize太多东西了可能会out of memory，怎么办呢？
在github有clojure更加高级的memoize package，可以搞些什么先进先出或者动态的换
入换出之类的memoize，在小内存机器上可以避免out of memory problem。

【在 l**b 的大作中提到】

: CLRS上面是不是有一个专门的recursion+cache的叫法？memoization？那个大牛给定义
: 一下。DP还是好难想出来啊。

f*72012-01-05 08:01

27 楼

DP的定义是递归的
我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
by nature就是递归的思想。----最优子结构
对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
entry里。----重复子问题
这两个是DP的重要性质。
CLRS对于DP的算法有两种
1. Top-down recursion with memoization
这种写法就是递归，用数组保存子问题的solution。
好处在于解决某些大问题，并不需要tabulate所有的子问题的时候，我们可以节约计算
时间，类似lazy evaluation。子问题只有在需要的时候才会被计算。第二个好处是直
接从定义出发，递归结构清晰，易于调试。
坏处是递归函数需要OS维护stack frame，如果问题规模太大，可能会stack overflow
，并且维护stack frame也是time-consuming task（正如递归计算fib数列）
2. Bottom-up tabulation
这种写法就是迭代。先初始化base case，然后按照某种顺序依次解决子问题，使得我
们要解决某个大问题的时候，它所需要的子问题都已经解决了。这个过程就是
tabulation。
然后在table中找寻原问题的最优解。这个最优解不一定是数组的最后一个元素，或者
矩阵的右下角。比如，longest increasing subsequence，最优解可能存在数组的任意
一个entry。比如，poj的1163，最优解在矩阵的最后一行。
tabulation的方式有很多种，比如一维（最大字段和），二维row-major（机器人从左
上角走到右下角），二维沿对角线（最大回文子串）。tabulation的好处是，迭代写法
，不需要stack space。坏处是需要解决所有子问题。
关于space efficient的tabulation
取决于解决大问题的时候，需要之前几个时刻的状态。
比如最大字段和，我们只需要之前一个position的最优解，所以O(n)的空间可以优化到
O(1)。比如fib数列，我们只需要之前两个时刻的solution，所以大家都用两个变量反
复迭代，空间复杂度是O(1)，其本质是维护一个固定长度的滚动数组fib[2]
PS：有的问题只能用memoization解决，比如poj的1088
我也是这几个月才学习DP的，不是高手。
这是我的见解，有不对的但求指教~~~谢谢

p*22012-01-05 08:01

28 楼

我觉得说的很准确。跟我理解的一样。没有提到的就是，我觉得DP初始化还是蛮tricky
的。需要点经验。

【在 f*****7 的大作中提到】

: DP的定义是递归的
: 我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
: 。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
: by nature就是递归的思想。----最优子结构
: 对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
: 已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
: 果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
: entry里。----重复子问题
: 这两个是DP的重要性质。
: CLRS对于DP的算法有两种

O*i2012-01-05 08:01

29 楼

DP就是利用一维或者二维的数组，找递推关系式，也就是状态转移方程。常数空间和三
维以上空间在实际面试中不多见。
难就难在写出递归方程。
不用说背包问题，就连经典的扔鸡蛋题(虽然有巧妙的小学生算法, 1+2+...+14恰好刚
大于100)本质也是DP。

O*i2012-01-05 08:01

30 楼

最简单的DP，就是兔子问题的Fibonacci数列。
次简单的是二项式定理的组合数公式，也就是贾宪三角，杨辉三角，帕斯卡三角。每个
数等于肩膀上两个数的和。
那个leetcode的题，从矩阵左上角走到右下角的不同走法，中学生直接写出组合数的解
。而求组合数的值除了直接用公式，就是用杨辉三角。那题的DP解法，实际上就是在暗
中进行杨辉三角的迭代。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

O*i2012-01-05 08:01

31 楼

最霸气的DP是三维以上的，也只有ACM的张驰这类牛人才得心应手，堪比侍魂中的天霸
封神斩。一般的DP面试，能发出奥义弧月斩就够用了。
F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
则如果存在k，使得要么
1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
F[l1 + k][u1][l2 + k][u2]
2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
F[l1 + k][u1][l2][l2 + k - 1]
两者有一个真，则F[l1][u1][l2][u2]为真
因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3
决策为o(n), 总复杂度o(N^4)

w*x2012-01-05 08:01

32 楼

这个可以想的到，主要是实现很繁琐

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

: 最霸气的DP是三维以上的，也只有ACM的张驰这类牛人才得心应手，堪比侍魂中的天霸
: 封神斩。一般的DP面试，能发出奥义弧月斩就够用了。
: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3

d*x2012-01-05 08:01

33 楼

poj上遍地都是啊
列状态迁移函数，dp解决问题基本都要属于机械化题目了。。

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

: 最霸气的DP是三维以上的，也只有ACM的张驰这类牛人才得心应手，堪比侍魂中的天霸
: 封神斩。一般的DP面试，能发出奥义弧月斩就够用了。
: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3

a*m2012-01-05 08:01

34 楼

n维的正常，不一定就难，关键是状态和转移。不过确实一般比较花时间，面试题少见
。需要20多分钟能解决的dp问题应该都比较简单。

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

: 最霸气的DP是三维以上的，也只有ACM的张驰这类牛人才得心应手，堪比侍魂中的天霸
: 封神斩。一般的DP面试，能发出奥义弧月斩就够用了。
: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3

d*x2012-01-05 08:01

35 楼

我遇到过稍微复杂的
面试官听我说到状态转移函数，就说这个写起来确实比较复杂，你只要把状态转移函数
列出来就行，然后继续下一个。。。

【在 a********m 的大作中提到】

: n维的正常，不一定就难，关键是状态和转移。不过确实一般比较花时间，面试题少见
: 。需要20多分钟能解决的dp问题应该都比较简单。

a*m2012-01-05 08:01

36 楼

不错。赞。
dp定义确实有点混乱。俺也是从careerup开始真正学，所以以前经常把top-down算dp，
bottom-up不算。现在习惯了，不管3728全算。反正思路是一样的。

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

a*m2012-01-05 08:01

37 楼

恩。不然太浪费时间了，知道会就够了。

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

: 我遇到过稍微复杂的
: 面试官听我说到状态转移函数，就说这个写起来确实比较复杂，你只要把状态转移函数
: 列出来就行，然后继续下一个。。。

k*82012-01-05 08:01

38 楼

流弊～
二爷这几个总结的帖子太赞了，我要保存下来好好学习

O*i2012-01-05 08:01

39 楼

为什么是先看CC而且相信它的定义呢？
如果先看CLRS(有一章专门讲DP，还是期末必考的)，再看CC，就会觉得CC只把DP定义为
top-down的recursion + cache挺误导的。

【在 a********m 的大作中提到】

: 不错。赞。
: dp定义确实有点混乱。俺也是从careerup开始真正学，所以以前经常把top-down算dp，
: bottom-up不算。现在习惯了，不管3728全算。反正思路是一样的。

a*m2012-01-05 08:01

40 楼

以前没看过clrs或者没学这章也算正常吧。

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

: 为什么是先看CC而且相信它的定义呢？
: 如果先看CLRS(有一章专门讲DP，还是期末必考的)，再看CC，就会觉得CC只把DP定义为
: top-down的recursion + cache挺误导的。

O*i2012-01-05 08:01

41 楼

越来越坚信leetcode + peking2 + mitbbs的好回复应该能写出一本比Careercup更有深
度的书了。

【在 a********m 的大作中提到】

: 以前没看过clrs或者没学这章也算正常吧。

a*m2012-01-05 08:01

42 楼

careerup确实有不少可以提高的地方。但是目前来说还是对sde面试最有帮助的书之一
了。

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

: 越来越坚信leetcode + peking2 + mitbbs的好回复应该能写出一本比Careercup更有深
: 度的书了。

s*l2012-01-05 08:01

43 楼

这个dp的定义在careercup 150题的第几版里啊？
我不记得这么定义的啊 >_<

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

s*l2012-01-05 08:01

44 楼

你说的poj是这个吗？ http://poj.org/

【在 f*****7 的大作中提到】

: DP的定义是递归的
: 我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
: 。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
: by nature就是递归的思想。----最优子结构
: 对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
: 已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
: 果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
: entry里。----重复子问题
: 这两个是DP的重要性质。
: CLRS对于DP的算法有两种

c*t2012-01-05 08:01

45 楼

顶！
如果看到题很快能想到应该用DP,但却怎么也写不出DP公式，怎么提高？是不是数学基
础太差？

【在 p*****2 的大作中提到】

: 不断看到有新人学习DP，想谈谈我的感受。
: 我大概是去年底，今年初开始学习DP的。以前没有一点概念。去年G电面我的时候就出
: 了一道最简单的DP题，那时我根本不知道什么是DP，在提示下用recursion做出来的，
: 没有用cache。
: 开始学习DP是在careercup 150那本书上。下面是一些感受。
: 1. careercup定义的DP就是recursion+cache。这个定义指导了我很长时间。我认为这
: 个定义是DP的初级阶段，有误导性，使得我在练习的时候发现很多题型用这个定义套不
: 上。误导性在于： 1, recursion+cache是DP不错，但是DP并不等于recursion+cache。
: 2, recursion的DP并不优化，因此从recursion出发做DP不是个好思路。
: 2. 我后来理解的DP是这样子的。很简单就是推DP公式。也就是说怎么用F(n-i) 推导出

p*22012-01-05 08:01

46 楼

leetcode确实应该出书。careercup从算法来说还是有不少没有cover，也有不少题感觉
面试也不会出现。Leetcode上的真题性要强很多。我先总结总结看看有没有什么好思路
没有。我现在也是在这么个过程当中。平时总是做题，做到一定程度就想归归类了。

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

: 越来越坚信leetcode + peking2 + mitbbs的好回复应该能写出一本比Careercup更有深
: 度的书了。

w*x2012-01-05 08:01

47 楼

光leetcode阵容不够强大啊，二爷得上啊

【在 p*****2 的大作中提到】

:
: leetcode确实应该出书。careercup从算法来说还是有不少没有cover，也有不少题感觉
: 面试也不会出现。Leetcode上的真题性要强很多。我先总结总结看看有没有什么好思路
: 没有。我现在也是在这么个过程当中。平时总是做题，做到一定程度就想归归类了。

p*22012-01-05 08:01

48 楼

应该还是练得少。我觉得当时我写文章的时候推递推公式还经常需要从topdown开始入
手。现在碰到DP的话，基本就不需要那个思维过程了。一般的DP推公式还比较自然。只
是发现对于DP的初始化还不得心应手，需要化时间考虑，有些题一下还不能做对。看看
再过一段时间有没有提高了。

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

: 顶！
: 如果看到题很快能想到应该用DP,但却怎么也写不出DP公式，怎么提高？是不是数学基
: 础太差？

p*22012-01-05 08:01

49 楼

我是想呀。关键是leetcode看不上我呀。

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

:
: 光leetcode阵容不够强大啊，二爷得上啊

p*22012-01-05 08:01

50 楼

专门有这么一章。recursion and DP吧。

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

: 这个dp的定义在careercup 150题的第几版里啊？
: 我不记得这么定义的啊 >_<

t*a2012-01-05 08:01

51 楼

对了，还有另外一个偷懒的技巧
有些DP可以转化为ILP（整数/布尔线性规划）。对于这类题目只要列出约束和目标方程
，直接call gnu的ILP package就可以拿到最优解，程序都不用写了~
版上以前的一些DP题目就可以直接这样用R来解决的，比如背包啦，换硬币，3sum,
4sum之类的
这样的code其实是更加stable更容易维护。就是不知道面试时候这样搞面试官买不买帐

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

: 楼上的都是大牛，抛砖引玉，介绍介绍偷懒的办法
: clojure上面的DP可以用memoize recusion function来做，懒汉专用工具 :)
: 但是这样的recusion还是有可能stack overflow，怎么办呢？
: 懒汉的办法就是再构造一个lazy sequence从小到大call过去，就保证了recusion不太
: 会发生了
: 这样的话，如果memoize太多东西了可能会out of memory，怎么办呢？
: 在github有clojure更加高级的memoize package，可以搞些什么先进先出或者动态的换
: 入换出之类的memoize，在小内存机器上可以避免out of memory problem。

a*m2012-01-05 08:01

52 楼

可以保证收敛么？LP以前看了一点，了解不多。

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

: 对了，还有另外一个偷懒的技巧
: 有些DP可以转化为ILP（整数/布尔线性规划）。对于这类题目只要列出约束和目标方程
: ，直接call gnu的ILP package就可以拿到最优解，程序都不用写了~
: 版上以前的一些DP题目就可以直接这样用R来解决的，比如背包啦，换硬币，3sum,
: 4sum之类的
: 这样的code其实是更加stable更容易维护。就是不知道面试时候这样搞面试官买不买帐

c*t2012-01-05 08:01

53 楼

请问这是scramble string那道题的DP公式吗？这么复杂啊。

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

: 最霸气的DP是三维以上的，也只有ACM的张驰这类牛人才得心应手，堪比侍魂中的天霸
: 封神斩。一般的DP面试，能发出奥义弧月斩就够用了。
: F[l1][u1][l2][u2]表示s1的[l1, u1]是否能通过scramble得到s2的[l2, u2]
: 则如果存在k，使得要么
: 1. F[l1][l1 + k - 1][l2][l2 + k - 1] &&
: F[l1 + k][u1][l2 + k][u2]
: 2. F[l1][l1 + k - 1][u2 - k + 1][u2] &&
: F[l1 + k][u1][l2][l2 + k - 1]
: 两者有一个真，则F[l1][u1][l2][u2]为真
: 因为l1, u1, l2确定，则u2 = u1 - l1 + l2，所以状态总数为n^3

O*i2012-01-05 08:01

54 楼

对，不过还是让zhangchitc给分杀了。

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

: 请问这是scramble string那道题的DP公式吗？这么复杂啊。

f*72012-01-05 08:01

55 楼

yes

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

: 你说的poj是这个吗？ http://poj.org/

c*t2012-01-05 08:01

56 楼

太恐怖了。
这题用recursion简单很多，而且时间复杂度和DP一样的吧?

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

: 对，不过还是让zhangchitc给分杀了。

s*l2012-01-05 08:01

57 楼

啊。。。
你看的是第几版啊？
我就看的第四版我刚翻了一下就有一章叫recursion 没有 recursion and DP啊。。。
看内容和你说的很相似

【在 p*****2 的大作中提到】

:
: 专门有这么一章。recursion and DP吧。

p*22012-01-05 08:01

58 楼

5

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

: 啊。。。
: 你看的是第几版啊？
: 我就看的第四版我刚翻了一下就有一章叫recursion 没有 recursion and DP啊。。。
: 看内容和你说的很相似

t*a2012-01-05 08:01

59 楼

ILP在问题规模大的时候会挂掉。不过DP也是一样会挂的。我经验不多，不过还是感觉
ILP要比DP快一些，而且程序明显容易写和修改。

【在 a********m 的大作中提到】

: 可以保证收敛么？LP以前看了一点，了解不多。

a*m2012-01-05 08:01

60 楼

dp计算本身和brute force没大区别，只是复杂度提高而且是可以计算出来的，只要公
式对资源够，不可能挂。LP印象中是逼近为基础的吧，约束条件也不是那么容易写和修
改的。
快不快看情况了，dp多数容易问题都是o(n)到o(n^2)。当然特别复杂的不好说了。

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

: ILP在问题规模大的时候会挂掉。不过DP也是一样会挂的。我经验不多，不过还是感觉
: ILP要比DP快一些，而且程序明显容易写和修改。

t*a2012-01-05 08:01

61 楼

真的不可能挂么... 有兴趣的话去看看历年的google code jam吧，我觉得后几轮的比
赛题目DP就只能解决小数据集，遇到大数据立扑

【在 a********m 的大作中提到】

: dp计算本身和brute force没大区别，只是复杂度提高而且是可以计算出来的，只要公
: 式对资源够，不可能挂。LP印象中是逼近为基础的吧，约束条件也不是那么容易写和修
: 改的。
: 快不快看情况了，dp多数容易问题都是o(n)到o(n^2)。当然特别复杂的不好说了。

S*y2012-01-05 08:01

62 楼

高手太多了

d*42012-01-05 08:01

63 楼

mark

p*22012-01-05 08:01

64 楼

去年一道DP，我是用top down来过的，bottomup的很多都死掉了。

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

: 真的不可能挂么... 有兴趣的话去看看历年的google code jam吧，我觉得后几轮的比
: 赛题目DP就只能解决小数据集，遇到大数据立扑

P*r2012-01-05 08:01

65 楼

我的心得是多做题。多了以后感觉有了，高维的也不怕。

P*r2012-01-05 08:01

66 楼

这个公式就是recursion就可以推出来。

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

: 太恐怖了。
: 这题用recursion简单很多，而且时间复杂度和DP一样的吧?

p*22012-01-05 08:01

67 楼

刚做了一遍，其实没有想像的那么繁琐。
http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html

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

:
: 光leetcode阵容不够强大啊，二爷得上啊

t*a2012-01-05 08:01

68 楼

我好几年没去参加了..挺想今年用现学的clojure/lisp去玩
如果遇到可以用ILP做的DP，我就用R，反正google code jam不限制语言的 :)

【在 p*****2 的大作中提到】

:
: 刚做了一遍，其实没有想像的那么繁琐。
: http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html

p*22012-01-05 08:01

69 楼

你以前最好的成绩是多少呀？

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

: 我好几年没去参加了..挺想今年用现学的clojure/lisp去玩
: 如果遇到可以用ILP做的DP，我就用R，反正google code jam不限制语言的 :)

t*a2012-01-05 08:01

70 楼

说出来丢人，最好就是前1000或者前500什么的。

【在 p*****2 的大作中提到】

:
: 你以前最好的成绩是多少呀？

p*22012-01-05 08:01

71 楼

貌似前500就不错了吧。

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

: 说出来丢人，最好就是前1000或者前500什么的。

h*62012-01-05 08:01

72 楼

前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。

p*22012-01-05 08:01

73 楼

你是前50的水平。

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

: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。

p*22012-01-05 08:01

74 楼

你是前50的水平。

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

: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。

p*22012-01-05 08:01

75 楼

你是前50的水平。

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

: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。

p*22012-01-05 08:01

76 楼

你是前50的水平。

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

: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。

t*a2012-01-05 08:01

77 楼

传说打败前50的S级妖怪有机会捡到经验之书和贵族头环，二爷加油啊

【在 p*****2 的大作中提到】

:
: 你是前50的水平。

p*22012-01-05 08:01

78 楼

我差的太远了。去年第二轮第三次才进，然后就裸奔了。

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

: 传说打败前50的S级妖怪有机会捡到经验之书和贵族头环，二爷加油啊

l*i2012-01-05 08:01

79 楼

mark！

【在 f*****7 的大作中提到】

: DP的定义是递归的
: 我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
: 。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
: by nature就是递归的思想。----最优子结构
: 对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
: 已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
: 果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
: entry里。----重复子问题
: 这两个是DP的重要性质。
: CLRS对于DP的算法有两种