PyDP
自动将Python递归函数转化为记忆化搜索(动态规划变种)的装饰器
部署
将dp.py
放在你的源码可以引入的目录下即可。
使用
- 在代码中添加
from dp import dp
来引入dp装饰器 - 使用
@dp
修饰需要记忆化的函数
例子
这里提供两个例子,你可以尝试去掉@dp
来对比性能。
Fibonacci序列
from dp import dp
@dp
def fib(n): return fib(n-1)+fib(n-2) if n>1 else n
print(fib(100))
组合数
from dp import dp
@dp
def comb(n,m):
if n==0:return 1 if m==0 else 0
if m<0:return 0
return comb(n-1,m)+comb(n-1,m-1)
print(comb(100,30))
技术
参阅 http://www.dyx.name/posts/auto-dp.html 以获取技术原理的细节。
版本历史
- 1.0.0 第一个稳定版本
- 1.0.1 修复不支持无参数函数的bug