先看调用装饰器函数解决一个斐波那契求和的问题
def memo(f):
    cache = {}
    def memorized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memorized
 
@memo
def fib(n):
    if n == 0 or n == 1:
        return 1
    return fib(n-1) + fib(n-2)
 
def main():
    T = int(input().strip())
    for _ in range(T):
        n = int(input().strip())
        print(fib(n))
 
动态规划 DP（入门）
二、前提条件
如果没有 cache：

int fib(int n)
{
    if(n==0||n==1)
        return 1;

    return fib(n-1)+fib(n-2);
}

例如：fib(5)

会变成：fib(5)

├── fib(4)
│   ├── fib(3)
│   └── fib(2)
│
└── fib(3)
    ├── fib(2)
    └── fib(1)

继续展开：

fib(2)
fib(3)
fib(2)
会被反复计算。

三、什么叫重叠子问题

观察上图：fib(3)出现两次。
fib(2)出现三次。

实际上：fib(20)
里面：
fib(18)
fib(17)
fib(16)
...

会被算无数次。

这就是：重叠子问题
定义：同一个子问题被重复求解。

这是DP出现的第一个条件。

四、 cache 干了什么

第一次：fib(5)

需要：fib(4)

于是计算：fib(4)=5

然后：cache[4]=5
保存下来。

以后再需要：fib(4)

直接：return cache[4]

不再递归。

因此：
每个 fib(k)
只会真正计算一次

五、用 C 语言模拟 cache

 Python：

cache[n]=f(n)

在 C 里面可以写成：

int cache[1000];

初始化：

for(int i=0;i<1000;i++)
{
    cache[i]=-1;
}

表示：
-1
代表没算过
六、记忆化搜索
定义缓存
int cache[1000];
递归
int fib(int n)
{
    if(n==0||n==1)
        return 1;

    if(cache[n]!=-1)
        return cache[n];

    cache[n]=fib(n-1)+fib(n-2);

    return cache[n];
}
或者
int fib(int n)
{
    if(n==0||n==1)
    {
        return 1;
    }

    if(cache[n]==-1)
    {
        cache[n]=fib(n-1)+fib(n-2);
    }

    return cache[n];
}
模板就是这样：
int dfs(...)
{
    if(边界)
        return ...;

    if(memo[状态]==-1)
    {
        memo[状态]=递归计算;
    }

    return memo[状态];
}
主要还是要保持状态，不太方便，更好的方式是拿DP数组
七、执行过程

例如：fib(5)

第一次：cache[5]=-1

说明没算过。

于是：fib(4)+fib(3)

算完后：cache[5]=8保存。

以后再调用：

fib(5)

直接：return cache[5];

结束。

八、为什么这已经属于 DP

很多教材会说：

DP要写dp数组

实际上不准确。

写法：
递归+缓存
已经是DP。

学术名字：
Memoization
记忆化搜索

关系：

暴力递归

↓

加缓存

↓

记忆化搜索

↓

动态规划
九、DP到底在干什么
实际上DP只干一件事：

避免重复计算

例如：fib(30)暴力递归：算几十万次

记忆化搜索：

fib(0)
fib(1)
...
fib(30)

每个只算一次。

十、进一步观察
代码里：

fib(n)=fib(n-1)+fib(n-2)
其实可以写成：

dp[n]=dp[n-1]+dp[n-2]

这里：fib(n)
就是：状态 State

所以：dp[i]
表示第i项斐波那契数

十一、状态转移方程

DP最重要的东西：状态转移方程

对于斐波那契：dp[i]=dp[i−1]+dp[i−2]

意思：当前状态
由之前状态推出来

十二、为什么以后不用递归

fib(100)

会递归：100层

虽然有cache。

但还是有：函数调用开销

于是可以直接写：

dp[0]=1;
dp[1]=1;

然后：

for(i=2;i<=n;i++)
{
    dp[i]=dp[i-1]+dp[i-2];
}