2 qq 34119437 qq_34119437 于 2016.05.04 00:55 提问

动态规划与递归联系。

求教各位,以前一直觉得动态规划就是对递归的优化,最近发现并不是。我想请问各位动态规划和递归之间有什么联系吗?还是说动态规划和递归没关系。

6个回答

caozhy
caozhy   Ds   Rxr 2016.05.04 05:58
已采纳

动态规划和递归毫无关系,事实上也没有“递归优化”这种说法。
动态规划的思想是将要解决的问题转化为一系列逐步求解的问题并且逐步加以解决。动态规划避免了无意义的穷举,它强调逐步解决问题,让先前解决的结果可以作为后续解决问题的条件避免重复求解相同的问题。
举一个例子,最长公共子序列问题(我曾经解答过,完整代码在这里:http://ask.csdn.net/questions/237208),传统的穷举是那第一个字符串的任意子序列去匹配第二个的任何子序列,比如说比较abc和bcd,abc的所有子串是
a
b
c
ab
bc
abc
而bcd是
b
c
d
bc
cd
bcd
然后再把它们两两比较,找到b c bc,最后找到最长的bc。这是无意义的穷举。
用动态规划,我们将它们转化为后缀数组,然后排序
a
ab
abc
b
b-2
bc
bc-2
bcd-2
c-2
cd-2
d-2
注意,因为C语言可以用首地址+长度表示一个字符串,实际上我们并不需要穷举就能得到子串
我们把子串排列起来,自然相邻的字符串才能匹配上。所以只要比较相邻的就可以了。
为什么第二个方法要比第一个方法好,因为第一个方法做了很多重复的事情,如果a和b匹配不上,它和c更匹配不上,但是显然在没有序的集合里匹配,它就是在做重复工作。

动态规划的过程中局部、整体等都可以采用递归,也可以不用。比如如上算法,其中排序的环节,你就可以用快速排序,它就是一个递归分治的过程。

qq_34119437
qq_34119437 谢谢您的回答。太感谢了。
一年多之前 回复
havedream_one
havedream_one   2016.05.04 08:31

递归:将问题分解成子问题求解,从较小的问题逐渐逼近原始问题,很多时候只需要在f(n-1)中加入或移除某些东西或稍作修改就可以求得f(n)

动态规划与递归的区别:动态规划要将中间的结果缓存起来以备后续使用

CSDNXIAON
CSDNXIAON   2016.05.04 08:51

递归和动态规划
递归和动态规划
动态规划和递归
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

bobbylee0810
bobbylee0810   2016.05.04 13:56

动态规划主要是那个函数

qq547276542
qq547276542   2016.05.23 20:19

递归只是动态规划的一种实现方式
动态规划可以递归实现,也可以递推实现

BillCYJ
BillCYJ   2017.12.10 16:34

自顶向下的动态规划是用递归实现的,而自底向上的动态规划使用迭代实现的。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!