第8章 复杂依赖及其记忆体化

1. 问题分解依旧使用递归/归纳那一套，但是我们允许子问题之间出现重叠。
2. 通常情况下，DP算法都是通过反转相应的递归函数，使其对某些数据结构进行逐步迭代和填充（如某种多维数组）。
3. 对于python来说，在实现相关递归函数时直接从缓存中返回值。如果我们使用 同一个参数执行多次调用，其返回结果就会直接来自于缓存。记忆体化（memoization）

8.1 不要重复自己

Fibonacci

import datetime

def fib(i):
    if i < 2:
        return 1
    else:
        return fib(i-1)+fib(i-2)

start = datetime.datetime.now()
print(fib(34))
end = datetime.datetime.now()
print(end-start)

9227465
0:00:01.532390

当你使用$fib(34)$fib(34)，用时如上，这是指数级的算法。
我们实现用嵌套域封装一个临时函数

import datetime
from functools import wraps


def fib(i):
    if i < 2:
        return 1
    else:
        return fib(i-1)+fib(i-2)
def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap


start = datetime.datetime.now()
fib = memo(fib)
print(fib(34))
end = datetime.datetime.now()
print(end-start)

9227465
0:00:00

该内存华函数的思路就是缓存其自身的返回值。

memo函数是一个可重用性更好得解决方案，它被当做一种装饰器来设计：

import datetime
from functools import wraps

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def fib(i):
	if i<2:
		return 1
	else:
		return fib(i-1)+fib(i-2)
		
start = datetime.datetime.now()
print(fib(34))
end = datetime.datetime.now()
print(end-start)	

9227465
0:00:00

fib()函数被直接标志成了@memo,这样就能有效地大幅降低一些运行时间。
这与分治问题不同的在于其存在一些复杂的依赖关系，或者说我们面对的是一些互相重叠的子问题。

写成迭代版（DP版本），不仅更快，还可以避免因为递归深度过大而导致堆栈空间耗尽。迭代版本的实现通常会有一个专属构造的缓存，而不是@memo中看到的那种通用的“由参数元组组成的键值字典”。
这种自定义的缓存设计可以使DP算法应用于更多的低级编程语言，像我们@memo装饰器中这种抽象结构通常是不可用的。

若使用dict()直接操作不存在的key
_dict = dict()
_dict['a'] += 1  # KeyError: 'a'