p*****2
发帖数: 21240 | 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的话，应该面试就差不多了
。 |
f**********2
发帖数: 2401 | |
w**z
发帖数: 8232 | |
p*****2
发帖数: 21240 | 4
没有呀。我去年连DP都不会，面试全fail掉了。
【在 w**z 的大作中提到】
: 您工作还没着落呢？是不是挑花眼了？
|
H**********y
发帖数: 7928 | 5 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*****y
发帖数: 205 | 6 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**********y
发帖数: 14569 | 7 赞！进来学习一下。
【在 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**********e
发帖数: 1145 | |
w****x
发帖数: 2483 | 9
说的不错.我想补充一下:
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******u
发帖数: 397 | 10 赞总结，bless find dream job！ |
|
|
p*****2
发帖数: 21240 | 11 不断看到有新人学习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**********2
发帖数: 2401 | |
w**z
发帖数: 8232 | |
p*****2
发帖数: 21240 | 14
没有呀。我去年连DP都不会，面试全fail掉了。
【在 w**z 的大作中提到】
: 您工作还没着落呢？是不是挑花眼了？
|
H**********y
发帖数: 7928 | 15 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*****y
发帖数: 205 | 16 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**********y
发帖数: 14569 | 17 赞！进来学习一下。
【在 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**********e
发帖数: 1145 | |
w****x
发帖数: 2483 | 19
说的不错.我想补充一下:
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******u
发帖数: 397 | 20 赞总结，bless find dream job！ |
|
|
l*****a
发帖数: 14598 | 21 牛
【在 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**b
发帖数: 457 | 22 CLRS上面是不是有一个专门的recursion+cache的叫法？memoization？那个大牛给定义
一下。DP还是好难想出来啊。 |
d**********x
发帖数: 4083 | 23 CLRS上不是说过了关键就是最优子结构嘛。。。
【在 l**b 的大作中提到】
: CLRS上面是不是有一个专门的recursion+cache的叫法？memoization？那个大牛给定义
: 一下。DP还是好难想出来啊。
|
p*****2
发帖数: 21240 | 24 才注意这是去年3月份写的。看来这几个月都荒废了。没啥进步呀。 |
t****a
发帖数: 1212 | 25 楼上的都是大牛，抛砖引玉，介绍介绍偷懒的办法
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*****7
发帖数: 92 | 26 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*****2
发帖数: 21240 | 27
我觉得说的很准确。跟我理解的一样。没有提到的就是，我觉得DP初始化还是蛮tricky
的。需要点经验。
【在 f*****7 的大作中提到】
: DP的定义是递归的
: 我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
: 。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
: by nature就是递归的思想。----最优子结构
: 对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
: 已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
: 果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
: entry里。----重复子问题
: 这两个是DP的重要性质。
: CLRS对于DP的算法有两种
|
O******i
发帖数: 269 | 28 DP就是利用一维或者二维的数组，找递推关系式，也就是状态转移方程。常数空间和三
维以上空间在实际面试中不多见。
难就难在写出递归方程。
不用说背包问题，就连经典的扔鸡蛋题(虽然有巧妙的小学生算法, 1+2+...+14恰好刚
大于100)本质也是DP。 |
O******i
发帖数: 269 | 29 最简单的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******i
发帖数: 269 | 30 最霸气的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****x
发帖数: 2483 | 31
这个可以想的到，主要是实现很繁琐
【在 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**********x
发帖数: 4083 | 32 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********m
发帖数: 15480 | 33 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**********x
发帖数: 4083 | 34 我遇到过稍微复杂的
面试官听我说到状态转移函数，就说这个写起来确实比较复杂，你只要把状态转移函数
列出来就行，然后继续下一个。。。
【在 a********m 的大作中提到】
: n维的正常，不一定就难，关键是状态和转移。不过确实一般比较花时间，面试题少见
: 。需要20多分钟能解决的dp问题应该都比较简单。
|
a********m
发帖数: 15480 | 35 不错。赞。
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********m
发帖数: 15480 | 36 恩。不然太浪费时间了，知道会就够了。
【在 d**********x 的大作中提到】
: 我遇到过稍微复杂的
: 面试官听我说到状态转移函数，就说这个写起来确实比较复杂，你只要把状态转移函数
: 列出来就行，然后继续下一个。。。
|
k**8
发帖数: 186 | 37 流弊～
二爷这几个总结的帖子太赞了，我要保存下来好好学习 |
O******i
发帖数: 269 | 38 为什么是先看CC而且相信它的定义呢？
如果先看CLRS(有一章专门讲DP，还是期末必考的)，再看CC，就会觉得CC只把DP定义为
top-down的recursion + cache挺误导的。
【在 a********m 的大作中提到】
: 不错。赞。
: dp定义确实有点混乱。俺也是从careerup开始真正学，所以以前经常把top-down算dp，
: bottom-up不算。现在习惯了，不管3728全算。反正思路是一样的。
|
a********m
发帖数: 15480 | 39 以前没看过clrs或者没学这章也算正常吧。
【在 O******i 的大作中提到】
: 为什么是先看CC而且相信它的定义呢？
: 如果先看CLRS(有一章专门讲DP，还是期末必考的)，再看CC，就会觉得CC只把DP定义为
: top-down的recursion + cache挺误导的。
|
O******i
发帖数: 269 | 40 越来越坚信leetcode + peking2 + mitbbs的好回复应该能写出一本比Careercup更有深
度的书了。
【在 a********m 的大作中提到】
: 以前没看过clrs或者没学这章也算正常吧。
|
|
|
a********m
发帖数: 15480 | 41 careerup确实有不少可以提高的地方。但是目前来说还是对sde面试最有帮助的书之一
了。
【在 O******i 的大作中提到】
: 越来越坚信leetcode + peking2 + mitbbs的好回复应该能写出一本比Careercup更有深
: 度的书了。
|
s********l
发帖数: 998 | 42 这个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********l
发帖数: 998 | 43 你说的poj是这个吗？ http://poj.org/
【在 f*****7 的大作中提到】
: DP的定义是递归的
: 我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
: 。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
: by nature就是递归的思想。----最优子结构
: 对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
: 已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
: 果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
: entry里。----重复子问题
: 这两个是DP的重要性质。
: CLRS对于DP的算法有两种
|
c********t
发帖数: 5706 | 44 顶！
如果看到题很快能想到应该用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*****2
发帖数: 21240 | 45
leetcode确实应该出书。careercup从算法来说还是有不少没有cover，也有不少题感觉
面试也不会出现。Leetcode上的真题性要强很多。我先总结总结看看有没有什么好思路
没有。我现在也是在这么个过程当中。平时总是做题，做到一定程度就想归归类了。
【在 O******i 的大作中提到】
: 越来越坚信leetcode + peking2 + mitbbs的好回复应该能写出一本比Careercup更有深
: 度的书了。
|
w****x
发帖数: 2483 | 46
光leetcode阵容不够强大啊，二爷得上啊
【在 p*****2 的大作中提到】
:
: leetcode确实应该出书。careercup从算法来说还是有不少没有cover，也有不少题感觉
: 面试也不会出现。Leetcode上的真题性要强很多。我先总结总结看看有没有什么好思路
: 没有。我现在也是在这么个过程当中。平时总是做题，做到一定程度就想归归类了。
|
p*****2
发帖数: 21240 | 47
应该还是练得少。我觉得当时我写文章的时候推递推公式还经常需要从topdown开始入
手。现在碰到DP的话，基本就不需要那个思维过程了。一般的DP推公式还比较自然。只
是发现对于DP的初始化还不得心应手，需要化时间考虑，有些题一下还不能做对。看看
再过一段时间有没有提高了。
【在 c********t 的大作中提到】
: 顶！
: 如果看到题很快能想到应该用DP,但却怎么也写不出DP公式，怎么提高？是不是数学基
: 础太差？
|
p*****2
发帖数: 21240 | 48
我是想呀。关键是leetcode看不上我呀。
【在 w****x 的大作中提到】
:
: 光leetcode阵容不够强大啊，二爷得上啊
|
p*****2
发帖数: 21240 | 49
专门有这么一章。recursion and DP吧。
【在 s********l 的大作中提到】
: 这个dp的定义 在careercup 150题 的第几版里啊？
: 我不记得这么定义的啊 >_<
|
t****a
发帖数: 1212 | 50 对了，还有另外一个偷懒的技巧
有些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********m
发帖数: 15480 | 51 可以保证收敛么？LP以前看了一点，了解不多。
【在 t****a 的大作中提到】
: 对了，还有另外一个偷懒的技巧
: 有些DP可以转化为ILP（整数/布尔线性规划）。对于这类题目只要列出约束和目标方程
: ，直接call gnu的ILP package就可以拿到最优解，程序都不用写了~
: 版上以前的一些DP题目就可以直接这样用R来解决的，比如背包啦，换硬币，3sum,
: 4sum之类的
: 这样的code其实是更加stable更容易维护。就是不知道面试时候这样搞面试官买不买帐
|
c********t
发帖数: 5706 | 52 请问这是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******i
发帖数: 269 | 53 对，不过还是让zhangchitc给分杀了。
【在 c********t 的大作中提到】
: 请问这是scramble string那道题的DP公式吗？这么复杂啊。
|
f*****7
发帖数: 92 | 54 yes
【在 s********l 的大作中提到】
: 你说的poj是这个吗？ http://poj.org/
|
c********t
发帖数: 5706 | 55 太恐怖了。
这题用recursion简单很多，而且时间复杂度和DP一样的吧?
【在 O******i 的大作中提到】
: 对，不过还是让zhangchitc给分杀了。
|
s********l
发帖数: 998 | 56 啊。。。
你看的是第几版啊？
我就看的第四版 我刚翻了一下 就有一章 叫recursion 没有 recursion and DP啊。。。
看内容 和你说的很相似
【在 p*****2 的大作中提到】
:
: 专门有这么一章。recursion and DP吧。
|
p*****2
发帖数: 21240 | 57 5
【在 s********l 的大作中提到】
: 啊。。。
: 你看的是第几版啊？
: 我就看的第四版 我刚翻了一下 就有一章 叫recursion 没有 recursion and DP啊。。。
: 看内容 和你说的很相似
|
t****a
发帖数: 1212 | 58 ILP在问题规模大的时候会挂掉。不过DP也是一样会挂的。我经验不多，不过还是感觉
ILP要比DP快一些，而且程序明显容易写和修改。
【在 a********m 的大作中提到】
: 可以保证收敛么？LP以前看了一点，了解不多。
|
a********m
发帖数: 15480 | 59 dp计算本身和brute force没大区别，只是复杂度提高而且是可以计算出来的，只要公
式对资源够，不可能挂。LP印象中是逼近为基础的吧，约束条件也不是那么容易写和修
改的。
快不快看情况了，dp多数容易问题都是o(n)到o(n^2)。当然特别复杂的不好说了。
【在 t****a 的大作中提到】
: ILP在问题规模大的时候会挂掉。不过DP也是一样会挂的。我经验不多，不过还是感觉
: ILP要比DP快一些，而且程序明显容易写和修改。
|
t****a
发帖数: 1212 | 60 真的不可能挂么... 有兴趣的话去看看历年的google code jam吧，我觉得后几轮的比
赛题目DP就只能解决小数据集，遇到大数据立扑
【在 a********m 的大作中提到】
: dp计算本身和brute force没大区别，只是复杂度提高而且是可以计算出来的，只要公
: 式对资源够，不可能挂。LP印象中是逼近为基础的吧，约束条件也不是那么容易写和修
: 改的。
: 快不快看情况了，dp多数容易问题都是o(n)到o(n^2)。当然特别复杂的不好说了。
|
|
|
S******y
发帖数: 1330 | |
d*********4
发帖数: 409 | |
p*****2
发帖数: 21240 | 63
去年一道DP，我是用top down来过的，bottomup的很多都死掉了。
【在 t****a 的大作中提到】
: 真的不可能挂么... 有兴趣的话去看看历年的google code jam吧，我觉得后几轮的比
: 赛题目DP就只能解决小数据集，遇到大数据立扑
|
P******r
发帖数: 842 | 64 我的心得是多做题。多了以后感觉有了，高维的也不怕。 |
P******r
发帖数: 842 | 65 这个公式就是recursion就可以推出来。
【在 c********t 的大作中提到】
: 太恐怖了。
: 这题用recursion简单很多，而且时间复杂度和DP一样的吧?
|
p*****2
发帖数: 21240 | 66
刚做了一遍，其实没有想像的那么繁琐。
http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html
【在 w****x 的大作中提到】
:
: 光leetcode阵容不够强大啊，二爷得上啊
|
t****a
发帖数: 1212 | 67 我好几年没去参加了..挺想今年用现学的clojure/lisp去玩
如果遇到可以用ILP做的DP，我就用R，反正google code jam不限制语言的 :)
【在 p*****2 的大作中提到】
:
: 刚做了一遍，其实没有想像的那么繁琐。
: http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html
|
p*****2
发帖数: 21240 | 68
你以前最好的成绩是多少呀？
【在 t****a 的大作中提到】
: 我好几年没去参加了..挺想今年用现学的clojure/lisp去玩
: 如果遇到可以用ILP做的DP，我就用R，反正google code jam不限制语言的 :)
|
t****a
发帖数: 1212 | 69 说出来丢人，最好就是前1000或者前500什么的。
【在 p*****2 的大作中提到】
:
: 你以前最好的成绩是多少呀？
|
p*****2
发帖数: 21240 | 70
貌似前500就不错了吧。
【在 t****a 的大作中提到】
: 说出来丢人，最好就是前1000或者前500什么的。
|
|
|
h**6
发帖数: 4160 | 71 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。 |
p*****2
发帖数: 21240 | 72
你是前50的水平。
【在 h**6 的大作中提到】
: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。
|
p*****2
发帖数: 21240 | 73
你是前50的水平。
【在 h**6 的大作中提到】
: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。
|
p*****2
发帖数: 21240 | 74
你是前50的水平。
【在 h**6 的大作中提到】
: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。
|
p*****2
发帖数: 21240 | 75
你是前50的水平。
【在 h**6 的大作中提到】
: 前500就有体恤衫了吧。不过我荒废了两年没做竞赛题，现在可能比较难进前500了。
|
t****a
发帖数: 1212 | 76 传说打败前50的S级妖怪有机会捡到经验之书和贵族头环，二爷加油啊
【在 p*****2 的大作中提到】
:
: 你是前50的水平。
|
p*****2
发帖数: 21240 | 77
我差的太远了。去年第二轮第三次才进，然后就裸奔了。
【在 t****a 的大作中提到】
: 传说打败前50的S级妖怪有机会捡到经验之书和贵族头环，二爷加油啊
|
l****i
发帖数: 396 | 78 mark！
【在 f*****7 的大作中提到】
: DP的定义是递归的
: 我们要得到原问题的最优解，就得先算出若干个子问题的最优解，然后extend到原问题
: 。我们不断地把大问题归结为若干个小问题，最后就是解决base case。这种思维方式
: by nature就是递归的思想。----最优子结构
: 对于多个大问题，要解决它们所用到的子问题可能有重复。所以我们需要用cache记录
: 已经计算过的子问题，如果该子问题被解决过了，直接从cache中fetch子问题的解。如
: 果该子问题没有被解决，那么就解决这个子问题，并且将solution存在cache对应的
: entry里。----重复子问题
: 这两个是DP的重要性质。
: CLRS对于DP的算法有两种
|
