递归算法和动态规划的关系是什么呀?

发布网友发布时间：2022-04-30 02:43

共4个回答

热心网友时间：2023-10-08 21:55

总地来说是不同的算法。但一些递归算法可改写成动态规划。
动态规划是空间换时间的算法。当递归运算的中间结果要反复使用时，动态规划可能将指数速度的算法改进为多项式速度（但相应地，空间代价提高）

热心网友时间：2023-10-08 21:56

递归比较简单的，就是递推的逆向算法。例如已知a(10)且a(n)=f(a(n+1))，让你求a(1)。回溯是深度优先搜索必须要用到的方法，推荐你看下“八皇后问题”，看完就应该明白了。动态规划是一种以空间换时间的算法，也就是占用内存较大，但是时间效率比较高的分阶段算法。推荐你看看“拦截导弹”问题，“0/1背包问题”。动态规划先多看看题，然后再去理解概念比较好

热心网友时间：2023-10-08 21:56

没什么直接的关系
只是有些动规是用递归来实现的而已

热心网友时间：2023-10-08 21:57

动态规划算法是递归算法的一种情况，我们所用的图搜索策略中的很多算法都是基于动态规划的。

比如说最短路径算法