动态规划算法学习笔记。

1. 定义

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.

本质:是对问题状态的定义和状态转移方程的定义。

2. 解题思路

2.1. 将原问题分解为子问题

  • 把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决。比如，POJ 1163:数字三角形。
  • 子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。

2.2. 确定状态

在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个状态。一个状态对应于一个或多个子问题，所谓某个状态下的值，就是这个状态所对应的子问题的解。

所有状态的集合，构成问题的状态空间。状态空间的大小，与用动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里，一共有 $\frac{N\times(N + 1)}{2}​$ 个数字，所以这个问题的状态空间里一共就有 $\frac{N\times(N + 1)}{2}​$ 个状态。

整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个状态只需要经过一次，且在每个状态上作计算所花的时间都是和 $N$ 无关的常数。

用动态规划解题，经常碰到的情况是，$K$ 个整型变量构成一个状态 (如数字三角形中的行号和列号这两个变量构成状态)。如果这 $K$ 个整型变量的取值范围分别是 $N_1, N_2, ……, N_k$，那么，我们就可以用一个 $K$ 维的数组 $array[N_1][N_2] \dots [N_k]$来存储各个状态的值。这个值未必就是一个整数或浮点数，可能是需要一个结构才能表示的，那么 array 就可以是一个结构数组。一个状态下的值通常会是一个或多个子问题的解。

2.3. 确定一些初始状态(边界状态)的值

以数字三角形为例，初始状态就是底边数字，值就是底边数字值。

2.4. 确定状态转移方程

定义出什么是状态，以及在该状态下的值后，就要找出不同的状态之间如何迁移——即如何从一个或多个值已知的状态，求出另一个状态的值 (人人为我递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作状态转移方程。

数字三角形的状态转移方程:

$MaxSum[r][j] = \begin{cases} D[r][j], &r = N \cr Max(MaxSum[r+1][j], MaxSum[r+1][j+1]) + D[r][j], &otherwise \end{cases}$

3. 条件

在对状态和状态转移方程的定义过程中，需满足最优子结构，并且无后效性：

  • 最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
  • 无后效性：当前的若干状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

4. 和其他方法的异同

  • 递推：每个阶段只有一个状态
  • 贪心：每个阶段的最优状态都是由上一个阶段的最优状态得到
  • 搜索：每个阶段的最优状态是由之前所有阶段的状态的组合得到
  • 动态规划：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的。

5. 技巧

  • 递归到动态规划的一般转化方法：递归函数有 $n$ 个参数，就定义一个 $n$ 维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始，逐步填充数组，相当于计算递归函数值的逆过程。
  • 缓存，重叠子问题，记忆化，这三个名词，都是在阐述递推式求解的技巧。以 Fibonacci 数列 为例，计算第 100 项的时候，需要计算第 99 项和 98 项；在计算第 101 项的时候，需要第 100 项和第 99 项，这时候你还需要重新计算第 99 项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。上述的需要再次计算的第 99 项，就叫重叠子问题。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像缓存一样，这种方法，叫做记忆化，这是递推式求解的技巧。这种技巧，其实就是花费空间来节省时间。

6. 动态规划的三种形式

  • 记忆递归型

    • 优点：只经过有用的状态，没有浪费。递推型会查看一些没用的状态，有浪费!
    • 缺点：可能会因递归层数太深导致爆栈，函数调用带来额外时间开销。无法使用滚动数组节省空间。总体来说，比递推型慢。

  • 我为人人递推型：没有什么明显的优势，有时比较符合思考的习惯。个别特殊题目中会比人人为我型节省空间。

    我为人人

  • 人人为我递推型：在选取最优备选状态的值 $F_m, F_n, …, F_y$ 时，有可能有好的算法或数据结构可以用来显著降低时间复杂度。

    人人为我

7. 练习