数据结构与算法python版（4）-动态规划简介（python常用的数据结构与算法）

数据结构与算法python版（4）-动态规划简介（python常用的数据结构与算法）

斐波那契数列：Fn=Fn-1+Fn-2使用递归的算法，代码如下：

def fibnacci(n): if n==1 or n==2: return 1 else: return fibnacci(n-1)+fibnacci(n-2)if __name__=="__main__": print(fibnacci(10))

执行结果如下：

55

使用非递归算法实现，代码如下：

def fibnacci_no_recurision(n): rs=[0,1,1] for i in range(n-2): num=rs[-1]+rs[-2] rs.append(num) return rsif __name__=="__main__": print(fibnacci_no_recurision(10))

执行结果如下：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

上述两种算法，当n比较大时，使用递归算法的方式会很慢，因为上述递归算法存在一个问题就是存在大量的重复计算非递归的算法就可以理解为动态规划算法动态规划的核心思想就是递归式+重复子问题 即通过分析得出一种递归的关系，然后在这个递归的关系中存在许许多多的子问题，通过将这些子问题的状态或结果存起来，这样就可以避免想递归中的那些反复的重复计算，这就是动态规划

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。