阅读总结自动态规划之武林秘籍

1. 基本思想

1.1 将待求解问题分解为若干个子问题
1.2 通过求解子问题的解得到原问题的解
1.3 经分解后的子问题往往不是互相独立的
1.4 需要对已经解决的子问题答案进行保存，防止出现重复计算的情况

2. 基本要素

如何判断一个问题是否可以用动态规划来解决，可以参照动态规划的两个基本要素

  1. 最优子结构性质
  2. 重叠子问题性质

2.1 最优子结构性质

当问题的最优解包含了其子结构的最优解时，称该问题具有最优子结构性质

动态规划基本介绍 - 图1
例如，最短路径问题有如下的最优子结构

2.2 重叠子问题性质

  • 动态规划经分解得到的子问题往往不是互相独立的。
  • 如果经分解之后的子问题互相独立，比如二分查找经分解之后的子问题之间相互独立，不存在重叠子问题，所以不适用动态规划，更适合分治算法

2.2.1. 保存重叠子问题的解的常见方法

2.2.1.1 DP table （自底向上）
  • 自底向上建立一个表格，用于保存每个子问题的解，并返回表中的最后一个解

  • 实现：

    1. def fib(n):
    2.   records = []
    3.   records.append(0)
    4.   records.append(1)
    5.   for i in range(2,n+1):
    6.       records.append(records[i-1] + records[i-2])
    7.   return records

    2.2.1.2 备忘录方法（自顶而下）

  • 备忘录方法时动态规划算法的变形，

  • 与动态规划方法一样，备忘录方法用表格保存已经解决的子问题的解，在下次需要解决此子问题的时候，只要简单查看盖子问题的解，不需要重新计算
  • 以动态规划方法的不同：备忘录方法时自顶线下的
  • 操作过程：
    • 为每一个子问题建立一个记录项
    • 初始时，该记录项存入一个特殊值，代表该子问题尚未被解决
    • 求解过程中，先查看子问题对应的记录项
      • 若记录项时初始化的特殊值，代表该子问题未被求解，此时计算子问题的特殊值，并保存在记录项中
      • 若记录项存储的是不初始化的特殊值，代表该子问题已经被求解，只需从记录想中提取该子问题的答案即可

动态规划基本介绍 - 图2

  • 实现：
    def fib(n):
  initilizer = [-1] * (n+1)
  if initilizer[n] == -1:
      if n <= 1:
          initilizer[n] = n
      else:
          initilizer[n] = fib(n-1) + fib(n-2)
  return initilizer[n]

    3. 如何解决动态规划问题

    动态规划( Dynamic Programming, DP)是在多项式时间解决特定类型问题的一套方法论，且远远快于只是级别的蛮力方法，且动态规划的正确性是可以严格证明的。

四步法

  1. 辨别是不是一个动态规划问题
  2. 确定状态
  3. 建立状态之间的关系
  4. 为状态添加备忘录或者DP Table

3.1 辨别是不是一个动态规划问题

  • 一边情况下，需要求解最优解的问题（最短路径问题，最长公共子序列，最大字段和···），在一定条件下对排列进行计数的计数问题（丑数问题）或某些概率问题都可以考虑使用动态规划来解决
  • 所有动态规划问题都满足重叠子问题性质
  • 大多数冬天规划问题还满足最优子结构性质

3.2 确定状态

  • DP问题最重要的就是确定所有状态和状态之间的转移方程。

    什么是状态？

  • 状态 可以视为一组可以唯一标识给定问题中某个子问题解的参数。

  • 这组参数要尽可能的小（为了减少状态空间的大小）
  • 以斐波那契数例子：
    • 0，1，···，n就可以视为参数
    • DP[0]，DP[1]，···，DP[n]就是状态
    • DP[n] = DP[n-1] + DP[n-2]就是状态之间的转移方程
  • 背包问题：
    • index和weight是参数
    • DP[index][weight]是状态

3.3 构造状态转移方程

这是DP问题中最难的部分

例子：

  • 问题描述：给定3个数{1,3,5}，请问使用这三个数，有多少种方式可以构造出一个给定的数’n’

    设n=6，使用{1, 3, 5}则共有8种方式可以构造出n
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1

  • 问题思路：

    • 确定问题状态
      • 由于参数n可以唯一标识任意一个子问题，所以使用参数n来确定状态
      • 状态为：DP[n]
    • 计算DP[n]：
      • 求解出n等于1，2，3，4，5，6的状态值
      • DP[n=1]=1, DP[n=2]=1, DP[n=3]=2, DP[n=4]=3, DP[n=5]=5, DP[n=6]=8
    • 求解DP[7]
      • 给状态DP[n=6]的所有序列+1
      • 给状态DP[n=4]的所有序列+3
      • 给状态DP[n=2]的所有序列+5
      • DP[7] = DP[6]+DP[4]+DP[2]
      • DP[n] = DP[n-1]+DP[n-3]+DP[n-5]

  • 实现：

    def solve(n):
  if n < 0:        # 无效状态，返回0
      return 0
  if n == 0 or n == 1:    # n=0的时候，代表原始可用数字中存在该数，所以要记一次
      return 1
  return solve(n-1) + solve(n-3) + solve(n-5)

    3.4 为状态添加备忘录或者是DP Table

    动态规划中最简单的部分，仅需要存储子状态，以便下次使用子状态时直接通过查表实现

  • 实现：

    def solve(n):
  initilizer = [-1] * (n+1)
  initilizer[0] = 1
  initilizer[1] = 1
  initilizer[2] = 1
  initilizer[3] = 2
  initilizer[4] = 3
  initilizer[5] = 5

  for i in range(6, n+1):
      initilizer[i] = initilizer[i-1] + initilizer[i-3] + initilizer[i-5]

  return initilizer[n]

    4. 备忘录和DP Table的选择

    4.1 DP Table方法（自底而上的动态规划）

    状态转移过程

  • 设DP问题的基态为 dp[0] ，目标状态为 dp[n]

  • 如果从 dp[0] 开始转移，在遵循状态转移方程的情况下达到目标状态 dp[n] ，则是“自底向上”的方法

4.2 备忘录方法（自顶而下的方法）

状态转移过程

  • 设DP问题的基态为 dp[n] ，目标状态为 dp[n]
  • 如果从 dp[n] 开始转移，找到所有和 dp[n] 相关的子状态，并返回 dp[n]

4.3 比较

  1. 状态： DP Table 状态转移关系较难确定， 备忘录 状态转移关系较易确定
    1. 自顶向下推到较为容易
  2. 代码：当约束条件较多的情况下，
    1. DP Table 较为复杂；
    2. 备忘录 代码相对容易实现，只需要对递归代码进行改造
  3. 效率：
    1. DP Table 较快，可以直接从表中获取子状态
    2. 备忘录 由于大量的递归调用和返回状态操作，较慢
  4. 子问题的解：
    1. 当所有子问题的解都需要被计算一遍时， DP Table 通常比 备忘录 方法快常数量级
    2. 当求解问题的子问题空间中部分子问题不需要计算时， 备忘录 方法要由于 DP Table
  5. 表空间
    1. DP Table 一次填充所有子状态的解
    2. 备忘录 只需要填充需要的子状态的解