python自顶向下设计步骤-python实现自顶向下，自底向上.pdf
需积分: 5 97 浏览量
2022-05-01
16:18:20
上传
评论
收藏 165KB PDF 举报
python⾃顶向下设计步骤_python实现⾃顶向下，⾃底向上
常⽤的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等，这些思想有重叠的部分，当⾯对⼀个问题的时候，从这⼏个思路
⼊⼿往往都能得到⼀个还不错的答案。
本来想把动态规划单独拿出来写三篇⽂章呢，后来发现⾃⼰学疏才浅，实在是只能讲⼀些⽪⽑，更深⼊的东西尝试构思了⼏次，也没有什么
进展，打算每种设计思想就写⼀篇吧。
动态规划(Dynamic Programming)是⼀种⾮常有⽤的⽤来解决复杂问题的算法，它通过把复杂问题分解为简单的⼦问题的⽅式来获得最优
解。
⼀、⾃顶向下和⾃底向上
总体上来说，我们可以把动态规划的解法分为⾃顶向下和⾃底向上两种⽅式。
⼀个问题如果可以使⽤动态规划来解决，那么它必须具有“最优⼦结构”，简单来说就是，如果该问题可以被分解为多个⼦问题，并且这些
⼦问题有最优解，那这个问题才可以使⽤动态规划。
⾃顶向下(Top-Down)
⾃顶向下的⽅式其实就是使⽤递归来求解⼦问题，最终解只需要调⽤递归式，⼦问题逐步往下层递归的求解。我们可以使⽤缓存把每次求解
出来的⼦问题缓存起来，下次调⽤的时候就不必再递归计算了。
举例著名的斐波那契数列的计算：
#!/usr/bin/env python
# coding:utf-8
def fib(number):
if number == 0 or number == 1:
return 1
else:
return fib(number - 1) + fib(number - 2)
if __name__ == '__main__':
print fib(35)
有⼀点开发经验的⼈就能看出，fib(number-1)和fib(number-2)会导致我们产⽣⼤量的重复计算，以上程序执⾏了14s才出结果，现在，
我们把每次计算出来的结果保存下来，下⼀次需要计算的时候直接取缓存，看看结果：
#!/usr/bin/env python
# coding:utf-8
cache = {}
def fib(number):
if number in cache:
return cache[number]
if number == 0 or number == 1:
return 1
else:
cache[number] = fib(number - 1) + fib(number - 2)
评论0