[关闭]
@liweiwei1419 2019-01-18T06:06:53.000000Z 字数 3633 阅读 1219

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

动态规划

这一章节我们介绍“动态规划”的基础内容。

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

第 1 部分：从“斐波那契数列”认识“动态规划”

斐波那契数列的定义

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

代码实现：

  1. private int fib(int n) {
  2.     if (n == 0) {
  3.         return 0;
  4.     }
  5.     if (n == 1) {
  6.         return 1;
  7.     }
  8.     return fib(n - 1) + fib(n - 2);
  9. }

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

Java 代码：

  1. public class CalFib {
  2.     public static void main(String[] args) {
  3.         CalFib calFib = new CalFib();
  4.         int n = 40;
  5.         long start = System.currentTimeMillis();
  6.         int fib = calFib.fib(n);
  7.         long end = System.currentTimeMillis();
  8.         System.out.println("递归版计算结果：" + fib);
  9.         System.out.println("递归版耗时：" + (end - start));
  10.         long start1 = System.currentTimeMillis();
  11.         int fib2 = calFib.fib2(n);
  12.         long end1 = System.currentTimeMillis();
  13.         System.out.println("非递归版计算结果：" + fib2);
  14.         System.out.println("非递归版耗时：" + (end1 - start1));
  15.     }
  17.     // 递归方式
  18.     private int fib(int n) {
  19.         if (n == 0) {
  20.             return 0;
  21.         }
  22.         if (n == 1) {
  23.             return 1;
  24.         }
  25.         return fib(n - 1) + fib(n - 2);
  26.     }
  28.     // 非递归的方式
  29.     private int fib2(int n) {
  30.         int[] memory = new int[n + 1];
  31.         memory[0] = 0;
  32.         memory[1] = 1;
  33.         for (int i = 2; i < n + 1; i++) {
  34.             memory[i] = memory[i - 1] + memory[i - 2];
  35.         }
  36.         return memory[n];
  37.     }
  39. }

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

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

  1. 递归版计算结果：102334155
  2. 递归版耗时：565
  3. 非递归版计算结果：102334155
  4. 非递归版耗时：0

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

  1. 递归版计算结果：267914296
  2. 递归版耗时：1579
  3. 非递归版计算结果：267914296
  4. 非递归版耗时：0

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

  1. 递归版计算结果：701408733
  2. 递归版耗时：4179
  3. 非递归版计算结果：701408733
  4. 非递归版环版耗时：0

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

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

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

Java 代码：

  1. public class CalFib {
  2.     public static void main(String[] args) {
  3.         CalFib calFib = new CalFib();
  4.         int n = 40;
  5.         long start = System.currentTimeMillis();
  6.         int fib = calFib.fib(n);
  7.         long end = System.currentTimeMillis();
  8.         System.out.println("递归版：" + fib);
  9.         System.out.println("递归版调用次数：" +  count1);
  10.         System.out.println("递归版耗时：" + (end - start));
  11.         long start1 = System.currentTimeMillis();
  12.         int fib2 = calFib.fib2(n);
  13.         long end1 = System.currentTimeMillis();
  14.         System.out.println("循环版：" + fib2);
  15.         System.out.println("循环版调用次数：" + count2);
  16.         System.out.println("循环版耗时：" + (end1 - start1));
  17.     }
  19.     static int count1 = 0;
  20.     static int count2 = 0;
  21.     // 递归方式
  22.     private int fib(int n) {
  23.         count1++;
  24.         if (n == 0) {
  25.             return 0;
  26.         }
  27.         if (n == 1) {
  28.             return 1;
  29.         }
  30.         return fib(n - 1) + fib(n - 2);
  31.     }
  33.     // 非递归的方式
  34.     private int fib2(int n) {
  35.         int[] memory = new int[n + 1];
  36.         memory[0] = 0;
  37.         memory[1] = 1;
  38.         for (int i = 2; i < n + 1; i++) {
  39.             count2++;
  40.             memory[i] = memory[i - 1] + memory[i - 2];
  41.         }
  42.         return memory[n];
  43.     }
  45. }

以 为例，运行结果如下：

  1. 递归版：102334155
  2. 递归版调用次数：331160281
  3. 递归版耗时：616
  4. 循环版：102334155
  5. 循环版调用次数：39
  6. 循环版耗时：0

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

image-20190118134120642

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

“重叠子问题”的一个特点是：递归调用虽然是调用自己，但是连传递的参数都有很多重复。想想我们之前学习递归的时候，曾经遇到过这样一个现象，递归调用其实也是顺序执行，函数一层一层调用，只不过调用的是自己，但是参数不同。

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

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

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

Java 代码实现：

  1. private static int[] memory;
  3. // 递归方式
  4. private int fib(int n) {
  5.     count1++;
  6.     if (n == 0) {
  7.         return 0;
  8.     }
  9.     if (n == 1) {
  10.         return 1;
  11.     }
  12.     if (memory[n] == -1) {
  13.         memory[n] = fib(n - 1) + fib(n - 2);
  14.     }
  15.     return memory[n];
  16. }

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

  1. 递归版：1489622139
  2. 递归版调用次数：7999
  3. 递归版耗时：2
  4. 循环版：1489622139
  5. 循环版调用次数：3999
  6. 循环版耗时：0

什么是“记忆化搜索”？

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

什么是“动态规划”？

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

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

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.

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

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

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注