青蛙与缓存：简化实用版动态规划

1. 从一只青蛙说起

话说有一只青蛙，想要跳下n级台阶下水塘，它每次可以跳1个台阶或者2个台阶，那么请问它一共有多少种跳法下水塘(比如，n=30时)？

用数学的语言来看，我们需要求一个青蛙跳的函数f(n)，对这种自变量取值为非负整数的函数，我们可以从比较小的情况开始考虑，不难得到f(1)=1, f(2)=2，问题是以后的穷举越来越麻烦。

想象你就是那只青蛙，面对n级台阶，第一次你可以先跳1级，那么剩下n-1级，有f(n-1)种跳法，第一次也可以跳两级，那么剩下n-2级，有f(n-2)种跳法，所以这个问题的答案并不陌生，是神奇的斐波拉契数列：

\[\begin{aligned} F_{0} &=0 \\ F_{1} &=1 \\ F_{n} &=F_{n-1}+F_{n-2} \quad(\mathrm{n} \geq 2) \end{aligned}\]

解决这类求函数值问题的第一步，是找到一个递推式。我们把递推式翻译成python代码：

def fib(n):
    if n==0:
        return 1
    if n==1:
        return 1
    return fib(n-1)+fib(n-2)

%%time
fib(30)

Wall time: 269 ms
832040

运行时间284ms，有够慢的，为什么慢？因为重复计算实在太多，以计算f(5)为例，调用关系如下：

f(5)==>f(4), f(3)
f(4)==>f(3), f(2), f(3)==>f(2), f(1)
f(3)==>f(2), f(1), f(2)==>f(1), f(0), f(2)==>f(1), f(0), f(1)
f(2)==>f(1), f(0), f(1), f(1), f(0), f(1), f(0), f(1)
f(1), f(0), f(1), f(1), f(0), f(1), f(0), f(1)

那么一个很自然的想法是我们把中间计算结果都缓存下来，幸运的是，python中自带了这个“电池”。

from functools import lru_cache
@lru_cache()
def fib(n):
    if n==0:
        return 1
    if n==1:
        return 1
    return fib(n-1)+fib(n-2)

%%time
fib(30)
Wall time: 0 ns
832040

快到没计量出时间来。python中lru_cache的基本原理是构建一个字典，字典的key为调用参数，value就是该参数的计算结果。大致等价于如下代码：

def fib(n):
    if n in fib.cache:
        return fib.cache[n]
    if n==0:
        ans = 1
    elif n==1:
        ans = 1
    elif:
        ans = fib(n-1)+fib(n-2)
    fib.cache[n] = ans
    return ans
fib.cache = {}

当然，针对这个问题，我们可以使用更加细致的缓存方法，乃至去掉递归改用循环（相当于只保留两个缓存，大大减少了空间占用，但是如果我们要反复计算各个n值，那么或许前一个方法才更合适）：

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a

本题等同于 leetcode 70, 在leetcode上的python3解答如下：

from functools import lru_cache
class Solution:
    @lru_cache()
    def climbStairs(self, n: int) -> int:
        if n==0:
            return 1
        if n==1:
            return 1
        return self.climbStairs(n-1)+self.climbStairs(n-2)

执行用时52 ms，内存消耗13.2MB。

2. 简化实用版动态规划

我们从这只青蛙中取得比较通用的启示，解决类似的可构造递推函数的问题：

寻找一个递推关系，建立递归函数，问题变成多个子问题的求解；
为了防止反复计算同样的子问题，使用缓存，用空间换时间。

在一般的算法教材或面试题解中，会花不少时间来设计这个缓存结构，在实际的工程问题中，我们可能对多使用一些缓存空间没有那么敏感，因此只需要开发递归函数，再加上通用的缓存方案就基本解决问题了。只有在缓存空间成为问题时，我们才需要进一步去考虑适应问题的更小的缓存。

为了检验这套方案，我们再看几道题，直接在leetcode上再找几个来刷。

2.2 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

示例:

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

将矩阵中每个位置作为右下角，求最小路径和，不难得到如下递推公式： \(\begin{aligned} f(0, 0)&=grid(0, 0) \\ f(x, 0)&=f(x-1, 0)++grid(x, 0) \quad(x>0) \\ f(0, y)&=f(0, y-1)++grid(0, y) \quad(y>0) \\ f(x, y)&=min(f(x-1, y), f(x, y-1))+grid(x, y) \quad(x>0, y>0) \end{aligned}\)

在leetcode中翻译成python3代码如下：

from functools import lru_cache
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        self.grid = grid
        return self.f(len(grid)-1, len(grid[0])-1)
    @lru_cache()
    def f(self, x, y):
        if x == 0 and y == 0:
            return self.grid[0][0]
        elif y == 0:
            return self.f(x-1, 0) + self.grid[x][0]
        elif x == 0:
            return self.f(0, y-1) + self.grid[0][y]
        else:
            return min(self.f(x-1,y), self.f(x,y-1)) + self.grid[x][y]

执行耗时1052ms，内存消耗13.9M。

1. 从一只青蛙说起

2. 简化实用版动态规划

2.1 最大子序和

2.2 最小路径和