动态规划问题基本框架

##0x00 起源和定义
动态规划(dynamic programming)其中 programming 是数学领域中规划,优化的意思
1956年Bellman的著作 dynamic programming 首次提出动态规划这个概念。
著名的最短路算法—— bellman-ford 算法也用 bellman 来命名。

动态规划有以下几个概念:

  • 阶段
  • 状态
  • 决策
  • 无后效性

##0x01 抽象描述

  • 一个系统,有若干状态,每个状态下有若干合法的操作,称为决策,决策会改变系统状态,决策会带来收益(或费用)。
  • 在初始状态下,我们需要求最终状态下的最大收益或最小费用。
  • 在每个阶段,选择一些决策,状态随之改变。
  • 收益只取决与当前状态和决策,即无后效性。
    比如:我们在状态3下的收益是 f(状态3),只取决于状态3的决策,与之前任何状态无关。
  • 使得系统达到终止状态时,总收益最大(或费用最小),总收益一般指各阶段收益的总和

##0x02 特点和步骤

  • 特点:子问题有大量重叠
    • 应对:打表避免重复计算
      表格记录每个状态的最大收益
  • 步骤
    1. 确定状态集合和收益
    2. 初始状态、终止状态
    3. 确定决策集合
    4. 是否无后效(这一步非常重要)
    5. 收益如何表示(写出递推式)

下面详细分析来两个例题:LIS 以及 TSP 问题

##0x03 最长单增子序列LIS

Longest Increasing Subsequence (LIS) 最长单增子序列问题
给定一个数列,求它的最长单增的子序列。
例如 给定 10,4,20,10,15,13 则 {4,10,15} 和 {4,10,13} 都是解

确定状态

  • 收益和状态:以第i项结尾的最长单增子序列的长度f(i)
  • 初始状态 f(0) = 0
  • 终止状态 max{f(1),f(2),f(3)…f(n)}
  • 决策:已知全部 f(x), x < i,如果 ai > ax,则显然可以把 ai 连接在 ax 的后面。
  • 无后效性:f(i) 只与决策x 相关
  • 收益表示: 定义 f(i) = max{f(x)| x < i 且 ai > ax} + 1, 如果该集合是空集,则对应 max 值为 0

分析

  • 时间复杂度
    • 枚举i
    • 枚举x,找到最大的满足条件的x
    • O(n2)
  • 空间复杂度
    • 存储每个f(i) O(n)
  • 如何得到解?
    • 记录决策:对每个f(i)记录得到它的决策x

代码待补充

##0x04 旅行商问题TSP

TSP (Traveling Salesman Problem)
n 个城市,任意两个城市之间有一定距离,从一个城市出发经历所有的城市一次并且仅仅一次,
最终回到起点,使得所有距离最短? (最小代价圈)

确定状态

  • 顺序?假设已经经历了 ABCDE 这5个城市,最终在城市 E,那么 A,B,C,D 的顺序重要么?
  • f(s,x) 表示状态
    • s 表示经历过的城市集合。
    • X 表示最后一个城市,在集合s里
    • f(s,x) 表示经过s集合里那些城市,最终在城市x时所经过的最小距离。
  • 初始状态:f({1},1) = 0,假设从城市1 开始
  • 终止状态:f({1,2,3,…n},1)=?
  • 决策:在状态(s, x)找到一个不在集合s里的城市y,若从x走到y,则 f(s,x) + distance(x,y) 是一个经过集合 sUy 城市的路径。
  • 无后效性:收益只取决于状态(s,x)和决策y

分析

  • 费用表示: f(s,x) = min {f(s – x, y) + distance(y,x) }其中s-x表示从集合s中去掉城市x之后的集合, y在集合s-x中
  • 注意点: 最后回到起点的状态有点特殊,因为起点已经在集合里
  • 复杂度
    • 集合数 2n
    • 状态数 2n * n
    • 时间
      • 枚举s, x, y,所以总复杂度O(2n * n2)
    • 空间
      • O(2n * n)

总结

  • 函数 f(state) 的自变量 state 可以是一个复杂的对象,而不一定是简单的一个整数
    • 实现 java 里的各种 Map, C++ 里的 map, python 里的 dictionary
  • 本题是著名的 NPC 问题,我们的算法并不是多项式的
  • 如果n比较小,可以用位运算表示集合

代码待补充

接下来简析两个例子

##0x05 coins change
换硬币 (coins change)
用面值为C1,C2,C3…Cn的硬币,每种硬币面值数量不限,凑一定数量的钱,使得用硬币个数最少。

收益表示 f(x) 表示凑足x的钱最少的硬币数
确定初始状态 f(0)=0
确定递推式 f(x)=min{f(x-ci)}+1 i=1,2,3…n

##0x06 矩阵连乘最优加括号方式

两个 p q 和 q r 的矩阵相乘,要循环 p q r 次。
矩阵乘法满足结合律,给定若干个矩阵 A1,A2,…An,如何使用结合律加括号,使得总循环次数最少?
如A1 A2 A3 A4 可以通过加括号变成 A1 (A2 A3) A4 或 A1 A2 (A3 * A4) 等等

  • 定义 f(i,j) 表示从矩阵i乘到矩阵j最少的乘法次数
  • 初态 f(i,i) = 0 i=1,2,3,…n
  • 递推式 f(i,j) = min{f(i,k) + f(k + 1,j) + p q r}
    • 其中 1<=i<=k<j
    • 矩阵i…k乘积结果是p * q维
    • 矩阵k+1…j乘积结果是q * r维

##0x07 更多 dp 问题与提升

基本DP

  • 最长公共子序列(LCS)
  • 最短编辑距离
  • 最优二叉搜索树
  • 最优三角剖分
  • Bellman-ford算法
  • 0-1背包
  • 最大子段和

更难的DP

  • 树形dp
  • 先排序 后dp
  • 基于连通分量的dp——插头dp
  • dp加速——四边形不等式
  • LIS问题的O(nlogn)时间算法
  • 优化空间复杂度——滚动数组(本行结果只与“上一行”相关

##0x08 小结

  • 动态规划是什么?
    • 是在状态集合上的递推
      • f(new state) = f(old state) + payoff(decision)
      • 抽象理解状态
    • 是“最短路”
      • 图——广义有向无环图
        • 节点: 所有状态
        • 边:可能的决策在状态上的转换
      • 起点: 初始状态
      • 终点: 终止状态
  • 一般实现
    • 正向循环——自底向上
      • 思路简单,把所有从“小到到大”,求出所有状态对应值
      • 慢一些,但相对省空间
    • 递归——自顶向下
      • 要求 f(x)必须求f(y),进而必须求f(z)…
      • 只求需要的值
      • 相对快一些,但要消耗堆栈空间
  • 关于复杂度
    • 时间:O(状态数 * 每个状态下决策数)
    • 空间:O(状态数)
  • 本质
    • 把有影响的因素全部放进“状态”
    • 在状态图上的特殊递推

##Reference
半小时精讲动态规划-七月算法