回 帖 发 新 帖 刷新版面

主题:能不能讲讲动态规划啊?

能不能讲讲动态规划啊?书上都是数学推导,看不懂……举的例子又没有说明,看的很痛苦……那位好心人能不能讲一讲,举个详细的例子啊?谢谢啊!

回复列表 (共5个回复)

沙发

那我就简单说一下吧.
动态规划就是列也所有可能的方案,然后选出最优解.
比如一个人最多能拿得动100斤,现有40,50,70斤各一袋黄金.
就有如下方案:
1   40+50=90
2   70
90>70,所以选一袋40斤和一袋50斤.

板凳

有没有编程的例子啊?

3 楼

1楼的解释得也太简单了吧

动态规划都用于最优化问题,如果一个最优化问题可以分成k步完成,对于第i步,可以由前面的结果找出当前最优解,并最终找出全局最优解,这样的方法就是动态规划.书上有比我更严格好的定义.对于每一步都有一个状态,相临状态之前有状态转移方程,一般方程中都有min{}或max{},表示求当前最优解.一般用DP解出来的都需要O(n*n)的复杂度.

大致这样,有误请指出.

4 楼

我对DP的理解,它就像是步步为营,想扎营十里,必须从眼前开始一座一座地扎,最后才能扎到十里。还是不懂?-_-||

5 楼

动态规划在数据结构书中哪一章讲的啊?没找到,我的是严蔚敏的书

我来回复

您尚未登录,请登录后再回复。点此登录或注册