动态规划与递归联系。

Question

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

Answer 1

动态规划和递归毫无关系，事实上也没有“递归优化”这种说法。
动态规划的思想是将要解决的问题转化为一系列逐步求解的问题并且逐步加以解决。动态规划避免了无意义的穷举，它强调逐步解决问题，让先前解决的结果可以作为后续解决问题的条件避免重复求解相同的问题。
举一个例子，最长公共子序列问题（我曾经解答过，完整代码在这里：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更匹配不上，但是显然在没有序的集合里匹配，它就是在做重复工作。

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