贪心法，动态规划，分治法的区别 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

贪心法，动态规划，分治法的区别

贪心法，动态规划，分治法的区别# JobHunting - 待字闺中

c*e2015-01-20 08:01

1 楼

网上的一些资料人云亦云，感觉没有一个讲的通透的，哪位有推荐的资料？

w*k2015-01-20 08:01

2 楼

刷题吧，把各类典型题刷几个就懂了。

c*e2015-01-20 08:01

3 楼

你这属于夸夸其谈之流。
比如那个 jumpgame, 即可以贪心法，又可以 dp ,还可以 recursive.

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

: 刷题吧，把各类典型题刷几个就懂了。

d*i2015-01-20 08:01

4 楼

大部分人都是一知半解，我也是一知半解。可能智商不够，没办法全部领悟吧。
还是希望有大神出来指点各位迷途羔羊。

E*F2015-01-20 08:01

5 楼

我不是大神哈
贪心算法每一步只考虑当前最优，有些没法找到全局最优的也只能这么办
动态规划则是能把全局最优解分解成局部最优解，记录下各个状态下的局部最优解然后
综合起来
分治则是总体的结果要从局部的结果里去找，跟优化没直接关系

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

: 大部分人都是一知半解，我也是一知半解。可能智商不够，没办法全部领悟吧。
: 还是希望有大神出来指点各位迷途羔羊。

g*s2015-01-20 08:01

6 楼

慢慢领悟吧，不是一年，二年，三年，五年的事。

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

: 网上的一些资料人云亦云，感觉没有一个讲的通透的，哪位有推荐的资料？

M*72015-01-20 08:01

7 楼

非大神，上面有人说的不错。
说说自己的理解：
DP的一大要素是子问题最优解可以应用到所有包含该子问题的最优解中。
贪心如果满足这个要素，就是DP，或可以转化成DP；如果不满足，就是因为没有更好的
方法而找一个近似的，这种情况下就不是DP。
三种方法广义来说都是将问题降规模求解，只是我们一般说分治一般都是logN级的降，
例如那个MxN走矩阵或者LIS的方法是一个个递推，一般不叫分治。

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

: 网上的一些资料人云亦云，感觉没有一个讲的通透的，哪位有推荐的资料？