LeetCode 动态规划专题 1：“重叠子问题”和“记忆化搜索

这一章节我们介绍“动态规划”。很多朋友听到“动态规划”可能会望而生畏，觉得动态规划的问题都很复杂。但其实，动态规划本质依然是递归算法，只不过是满足特定条件的递归算法。在这一章，我们就来逐步解开动态规划的神秘面纱。

从“斐波那契数列”认识“动态规划”

斐波那契数列的定义

斐波那契数列是“递归”定义的，通过这个递归关系式，我们可以知道斐波那契数列中任意一个位置的数值。

Python 代码：

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

Java 代码：

private int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

代码本身用于计算是没有问题的，但是仔细一看就会发现，虽然使用“递归”实现了斐波那契数列在任意位置的值的计算，但是如果要我们手动计算的话，肯定不会这样做，因为这样做的话做了很多重复的工作。

事实上，我们手工计算斐波拉契数列的第 项的时候，是不会递归去求解的。于是我们可以很轻松地写出一个使用数组，通过循环实现的代码。

Java 代码：

public class CalFib {
    public static void main(String[] args) {
        CalFib calFib = new CalFib();
        int n = 40;
        long start = System.currentTimeMillis();
        int fib = calFib.fib(n);
        long end = System.currentTimeMillis();
        System.out.println("递归版计算结果：" + fib);
        System.out.println("递归版耗时：" + (end - start));
        long start1 = System.currentTimeMillis();
        int fib2 = calFib.fib2(n);
        long end1 = System.currentTimeMillis();
        System.out.println("非递归版计算结果：" + fib2);
        System.out.println("非递归版耗时：" + (end1 - start1));
    }

    // 递归方式，从上到下，有很多重叠子问题
    private int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    // 非递归的方式，从下到上
    private int fib2(int n) {
        int[] memory = new int[n + 1];
        memory[0] = 0;
        memory[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            memory[i] = memory[i - 1] + memory[i - 2];
        }
        return memory[n];
    }

}

斐波拉契数列的递归实现的问题

当 n = 40 的时候控制台输出：

递归版计算结果：102334155
递归版耗时：565
非递归版计算结果：102334155
非递归版耗时：0

当 n = 42 的时候控制台输出：

递归版计算结果：267914296
递归版耗时：1579
非递归版计算结果：267914296
非递归版耗时：0

当 n = 44 的时候控制台输出：

递归版计算结果：701408733
递归版耗时：4179
非递归版计算结果：701408733
非递归版环版耗时：0

可以发现，当 仅仅只是增加 的时候，递归版本的耗时在成倍地增加，但是非递归版的耗时却没有怎么改变。那么是什么造成了递归函数的执行效率如此之低呢？让我们来分析一下整个函数的执行流程。

打印递归实现的 fib 的调用次数认识到“重叠子问题”

我们对上面的代码在递归和循环的入口处增加计数器，来看看一看递归和循环分别调用的次数：

Java 代码：

public class CalFib {
    public static void main(String[] args) {
        CalFib calFib = new CalFib();
        int n = 40;
        long start = System.currentTimeMillis();
        int fib = calFib.fib(n);
        long end = System.currentTimeMillis();
        System.out.println("递归版：" + fib);
        System.out.println("递归版调用次数：" +  count1);
        System.out.println("递归版耗时：" + (end - start));
        long start1 = System.currentTimeMillis();
        int fib2 = calFib.fib2(n);
        long end1 = System.currentTimeMillis();
        System.out.println("循环版：" + fib2);
        System.out.println("循环版调用次数：" + count2);
        System.out.println("循环版耗时：" + (end1 - start1));
    }

    static int count1 = 0;
    static int count2 = 0;
    // 递归方式
    private int fib(int n) {
        count1++;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    // 非递归的方式
    private int fib2(int n) {
        int[] memory = new int[n + 1];
        memory[0] = 0;
        memory[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            count2++;
            memory[i] = memory[i - 1] + memory[i - 2];
        }
        return memory[n];
    }

}

以 为例，运行结果如下：

递归版：102334155
递归版调用次数：331160281
递归版耗时：616
循环版：102334155
循环版调用次数：39
循环版耗时：0

我们发现：这个问题我们画出的结构是一个树形结构。

重叠子问题

但是这个树形结构与我们在“回溯”问题中遇到的树形结构有一个很大的差别：存在大量的重复计算。这就是为什么上面使用“递归”计算斐波拉契函数执行效率低的原因。我们把这样的含有大量重复计算的树形问题的现象叫做“重叠子问题”。

“重叠子问题”的一个特点是：递归调用虽然是调用自己，但是传递的参数有很多重复。“递归”调用其实也是顺序执行，函数一层一层调用自己，虽然调用的是自己，但是传递的参数不同。

解决“重叠子问题” 要使用“记忆化搜索”

做过 Web 开发的朋友们一定知道，一个 Web 服务的性能瓶颈在数据库访问，那么优化数据库访问的一个措施就是对一些访问高频但是修改并不频繁的数据使用缓存。借助这个思路，我们对斐波拉契函数的递归版本也加上缓存，为此，我们引入一个数组。

下面的操作其实是套路，一定要非常熟练。

Python 代码：加入了记忆化搜索，即使用了缓存数组，以避免重复计算

memo = None

def _fib(n):
    if memo[n] != -1:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = _fib(n - 1) + _fib(n - 2)
    return memo[n]


def fib(n):
    global memo
    memo = [-1] * (n + 1)
    return _fib(n)

Java 代码实现：

private static int[] memory;

// 递归方式
private int fib(int n) {
    count1++;
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (memory[n] == -1) {
        memory[n] = fib(n - 1) + fib(n - 2);
    }
    return memory[n];
}

下面，我们就可以把 提高到 ，运行代码，控制台输出为：

递归版：1489622139
递归版调用次数：7999
递归版耗时：2
循环版：1489622139
循环版调用次数：3999
循环版耗时：0

Python 代码：虽然很简单，但是我们就可以称之为“动态规划”的解法

这个版本是最接近我们自己去计算斐波那契数列的第 项。想一想的确是这样，聪明的你一定不会递归去计算波那契数列的，因为我们的脑容量是有限，不太适合做太深的递归思考，虽然计算机对于递归在行，但是我们也没有必要让计算机做重复的递归工作。

def fib(n):
    memo = [-1] * (n + 1)
    memo[0] = 0
    memo[1] = 1

    for i in range(2, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

什么是“记忆化搜索”？

针对一个递归问题，如果它呈树形结构，并且出现了很多”重叠子问题”，会导致计算效率低下，“记忆化搜索”就是针对”重叠子问题”的一个解决方案，实际上就是”加缓存避免重复计算”。

“记忆化搜索”就是针对递归问题的树形结构中出现“重叠子问题”而效率低下的一个解决方案，即“加缓存”。

什么是“动态规划”？

由上面的介绍我们就可以引出动态规划的概念了。

1、“记忆化搜索”可以称之为“重叠子问题的加缓存优化”的实现，此时我们的思考路径是“自顶向下”，即为了解决数据规模大的问题，我们假设已经解决了数据规模较小的子问题；

2、“循环版本”的实现，我们的思考路径是“自下而上”，我们是真正地解决了数据规模较小的问题，然后一步一步地解决了数据规模较大的问题。

下面我们给出“动态规划”的官方定义：

dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure.

翻译：

将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

我们通常的做法是：使用“记忆化搜索”思考，使用“动态规划”实现。

总结

对于一个递归结构的问题，如果我们在分析它的过程中，发现了它有很多“重叠子问题”，虽然并不影响结果的正确性，但是我们认为大量的重复计算是不简洁，不优雅，不高效的，因此，我们必须将“重叠子问题”进行优化，优化的方法就是“加入缓存”，“加入缓存”的一个学术上的叫法就是“记忆化搜索”。

另外，我们还发现，直接分析递归结构，是假设更小的子问题已经解决给出的实现，思考的路径是“自顶向下”。但有的时候，“自底向上”的思考路径往往更直接，这就是“动态规划”，我们是真正地解决了更小规模的问题，在处理更大规模的问题的时候，直接使用了更小规模问题的结果。

（本节完）