动态规划问题基本框架

发表于   |  

##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
半小时精讲动态规划-七月算法