Dynamic Programming:动态编程分为如下几步:
将复杂问题拆分成多个较简单的子问题
对每个子问题只计算一次,然后使用数据结构(数组,字典等)在内存中存储计算结果
子问题的计算结果按照一定规则进行排序(如,基于输入参数)
当需要再次运算子问题时直接使用已存储的计算结果而非再次运算以提升求解性能
这种存储计算结果以备再次使用称之为:Memoization(这个词,不知道怎么翻译好)
以斐波那契数列为例来说明:
1、使用递归实现:
def fib(n): if n < 1: raise ValueError('参数n必须为大于0的整数') if n == 1 or n == 2: return 1 return fib(n-2)+fib(n-1)