s********u
发帖数: 1109 | 1 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
取决于之前所有解或者部分解。
而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
是这么个意思么。。 | k*********6
发帖数: 738 | 2 是的，greedy一旦made choice,就不再多考虑了，以后都base on这个choice. sub
problem 的其他借解都扔掉了。 通过local optimal try to 找到global optimal，可
以是近似的最优解。当然有的书说一定要保证greedy能找到最优解。但实际上有时候可
以根据具体问题采用greedy simplify problem.
DP是不放弃所有的choice, 保持所有sub problem 的solutions都考虑，最后因该一定
会找到最优解。所以DB经常有sub problem大量的重复计算，搞个大表memorize一下去
避免重复计算。
【在 s********u 的大作中提到】
: 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
: 我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
: 取决于之前所有解或者部分解。
: 而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
: 是这么个意思么。。
| f**********s
发帖数: 115 | 3 不是的。
贪心不是只取决于上一步(或上几步)的解。
我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
。 也就是说，根据现有的input就能知道怎么solve optimal solution， 将来进来的
input不会影响现在算出来的解。
相对的DP, 跟greedy不是互斥的。dp只是说， 一个problem可以break成几个类似的sub
-problem,并且sub-problem的解可以用来解开原本的problem | s********u
发帖数: 1109 | 4 嗯，我好像理解你的意思了。
就像这一段（维基百科）：
In other words, a greedy algorithm never reconsiders its choices. This is
the main difference from dynamic programming, which is exhaustive and is
guaranteed to find the solution. After every stage, dynamic programming
makes decisions based on all the decisions made in the previous stage, and
may reconsider the previous stage's algorithmic path to solution
一个简单的例子是，找硬币的问题，比如硬币面值是1,3,4.要组成6，贪心法就会得到(
4,1,1)，而dp则能解出（3,3）。
但我奇怪的是，如果按照这样的说法，我们平时绝大多数的dp题，难道实际上都是贪心
算法了。（或者把贪心看成dp的一种特殊情况？）
比如：leetcode的unique path，wordladder，或者subsequence问题（例如longest
increasing subsequence）。甚至最简单的fibnacci数列，因为f(n)都不会影响f(n-1)或
者更之前的决策，这样的话，都属于贪心算法？
sub
【在 f**********s 的大作中提到】
: 不是的。
: 贪心不是只取决于上一步(或上几步)的解。
: 我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
: 。 也就是说，根据现有的input就能知道怎么solve optimal solution， 将来进来的
: input不会影响现在算出来的解。
: 相对的DP, 跟greedy不是互斥的。dp只是说， 一个problem可以break成几个类似的sub
: -problem,并且sub-problem的解可以用来解开原本的problem
| k*********6
发帖数: 738 | 5 没有说greedy跟DP是互斥的，有说法greedy是DP的一个special case。其他没明白你说
的跟我说的有什么区别。。。
我觉得以下这个对于both greedy and DP都是true的，
〉我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
sub | s********u
发帖数: 1109 | 6 嗯，的确是有这么说法。就是贪心法可以看做是一个特例。
是我主贴写的是错的。
但如果是这样的话，我们讨论的绝大多数（几乎所有）的dp题实际都是贪心算法，就是
f(n)不会影响f(n-1),f（n-2)。。。f(1)的解。
【在 k*********6 的大作中提到】
: 没有说greedy跟DP是互斥的，有说法greedy是DP的一个special case。其他没明白你说
: 的跟我说的有什么区别。。。
: 我觉得以下这个对于both greedy and DP都是true的，
: 〉我对greedy的理解是， 当前的解就是最优解，不用管下面一个进来的input是什么。。
: sub
| f**********s
发帖数: 115 | 7 Greedy是一条线做下来，比如f(n)依赖f(n-1)
DP可以看成一个parallel universe，每一步有多种走法，你把每一步都走一遍，然后
看看每一种情况对下一步有什么影响。。
所以当每一步只有一个可能的走法时，dp就接近greedy了
纯个人理解，完全不严谨不学术呵呵
嗯，的确是有这么说法。就是贪心法可以看做是一个特例。是我主贴写的是错的。但如
果是这样的话，我们讨论的绝大多数（几乎所有）的dp题实际都是贪心算法，就是f(n)
不会影响f(n-1........
【在 s********u 的大作中提到】
: 嗯，的确是有这么说法。就是贪心法可以看做是一个特例。
: 是我主贴写的是错的。
: 但如果是这样的话，我们讨论的绝大多数（几乎所有）的dp题实际都是贪心算法，就是
: f(n)不会影响f(n-1),f（n-2)。。。f(1)的解。
| s********u
发帖数: 1109 | 8 今天想了一想，觉得可以分为两类问题：
1.节点空间两端收敛，中间可以发散，但是两端必须收敛。因此前驱节点一定能决定当
前节点（唯一解）。最典型的，就是leetcode的unique path，或者fibnacci数列。这
类问题，总是可以用dp bottom-up的做。
2.节点空间一端发散，也就是说前驱节点不能决定当前节点（可能有很多方向，很多解
）。这类问题一般可以用backtracking做。最典型的，自然是tree的dfs | s********u
发帖数: 1109 | 9 今天想了一想，觉得可以分为两类问题：
1.节点空间两端收敛，中间可以发散，但是两端必须收敛。因此前驱节点一定能决定当
前节点（唯一解）。最典型的，就是leetcode的unique path，或者fibnacci数列。这
类问题，总是可以用dp bottom-up的做。
2.节点空间一端发散，也就是说前驱节点不能决定当前节点（可能有很多方向，很多解
）。这类问题一般可以用backtracking做。最典型的，自然是tree的dfs | b***e
发帖数: 1419 | 10 Here’s a pretty extreme way of looking at it:
Every problem has a brute-force solution, that is, to search the space of
all the possible solutions. Usually the space of all the possible solutions
is a tree like structure, where starting from the root, there’s a bunch of
possibilities branching out, and on and on.
DP is still searching the full space, traversing all the nodes in the
possible solution space. The only thing it does better than naive brute-
force is that, DP would reuse the search results of the nodes that had been
traversed before.
Greedy algorithm, on the other hand, is not traversing the full search space
. It plays as an oracle and cleverly picks up a path from the root leading
to the solution node. But usually one needs to prove that this path is
truly leading to the solution, and that’s the hard part.
If you look at the real tricky graph theory algorithms, most of them are
greedy.
【在 s********u 的大作中提到】
: 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
: 我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
: 取决于之前所有解或者部分解。
: 而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
: 是这么个意思么。。
| s*****n
发帖数: 994 | 11 我感觉不是，我觉得是F和G的差别，dp里面F肯定是对的，可以证明的，贪心里面的G只
是local optimal，无法证明global optimal
【在 s********u 的大作中提到】
: 看了不少这方面的讨论，写的很玄乎。以前学的时候就没太明白。
: 我感觉是，动态规划就是f(n) = F( n,f(n-1),f(n-2),f(n-3)....f(1) )，就是当前解
: 取决于之前所有解或者部分解。
: 而贪心算法则是f(n) = G( n,f(n-1))，也就是当前解只取决于前一步的解。
: 是这么个意思么。。
| c*****e
发帖数: 3226 | 12 well said.
solutions
of
been
space
【在 b***e 的大作中提到】
: Here’s a pretty extreme way of looking at it:
: Every problem has a brute-force solution, that is, to search the space of
: all the possible solutions. Usually the space of all the possible solutions
: is a tree like structure, where starting from the root, there’s a bunch of
: possibilities branching out, and on and on.
: DP is still searching the full space, traversing all the nodes in the
: possible solution space. The only thing it does better than naive brute-
: force is that, DP would reuse the search results of the nodes that had been
: traversed before.
: Greedy algorithm, on the other hand, is not traversing the full search space
| d***n
发帖数: 832 | 13 说得很好
DP很多时候要解决所有的子问题，跟Brute Force相比优点是解决得很快，因为消除了
重复计算
Greedy用一个或多个简单rules，只解决基本一部分子问题，认为局部最优最导致全局
最优，这对不少问题是适用的。DP跟greedy相比是有些问题greedy没法找到全局最优方案
另外一方面我发现有些同学在面试中喜欢上DP，喜欢用DP作为终极利器。可是很多时候
面试官都没搞清楚什么DP，而且确实有比DP好的方案(不一定表现在快，而是表现在可
读性可维护性)
个人觉得把DFS研究得很深比DP更有用
如果DFS研究透了再研究一下DP
solutions
of
been
space
【在 b***e 的大作中提到】
: Here’s a pretty extreme way of looking at it:
: Every problem has a brute-force solution, that is, to search the space of
: all the possible solutions. Usually the space of all the possible solutions
: is a tree like structure, where starting from the root, there’s a bunch of
: possibilities branching out, and on and on.
: DP is still searching the full space, traversing all the nodes in the
: possible solution space. The only thing it does better than naive brute-
: force is that, DP would reuse the search results of the nodes that had been
: traversed before.
: Greedy algorithm, on the other hand, is not traversing the full search space
|
|
