动态规划学习

题目特点

• 计数
  • 有多少种方式走到右下角
  • 有多少种方法选出k个数使得和是sum
• 求最大最小值
  • 从左上角走到右下角路径的最大数字和
  • 最长上升子序列长度
• 求存在性
  • 取石子游戏，先手是否必胜
  • 能不能选出k个数使得和是sum

动态规划组成部分

https://www.lintcode.com/problem/669/

提出问题：给出面值2,5,7三种硬币，要求拼出27元，求最少需要多少硬币？

一、确定状态

• 两个意识

  • 最后一步

  • 子问题

• 原问题：最少用多少枚拼出27

• 转化子问题：最少用多少枚硬币拼出27-a_k

• 设状态f(X) = 最少用多少枚硬币拼出X

• 子问题：

  • 最后一枚硬币a_k可能为2,5或7，

    • 若a_k是2，则 f( 27 ) = f( 27 - 2 ) + 1
    • 若a_k是5，则 f( 27 ) = f( 27 - 5 ) + 1
    • 若a_k是7，则 f( 27 ) = f( 27 - 7 ) + 1

  • 要求最少硬币数，即：
    $$
    f(27) = min(f(27-2)+1,f(27-5)+1,f(27-7)+1)
    $$

二、转移方程

把括号换为中括号
$$
f[X] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
$$

三、初始条件和边界情况

• 边界情况

  • 若x-2，x-5或x-7小于0怎么办？什么时候停下来？

    • 若不能拼出Y，则定于f[Y]=+∞

    • 如：f[-1] = f[-2] = … = +∞

    • 此时

    • $$
      f[1] = min{f[-1]+1,f[-4]+1,f[-6]+1} = +∞
      $$

    • 即：拼不出来1

• 初始条件：f[0] = 0

四、计算顺序

• 计算顺序：f[0]，f[1]，f[2] …, f[27]。

总结

1. 确定状态

   • 最后一步（最优策略中使用最后一枚硬币a_k）
   • 化成子问题（最少的硬币拼出更小的面值27-a_k）

2. 转移方程

   • f[X] = min ( f[X-2]+1, f[x-5]+1, f[X-7]+1 )

3. 初始条件和边界情况

   • f[0] = 0
   • 若不能拼出Y，f[Y] = 正无穷

4. 计算顺序

   • f[0], f[1], f[2], …

常见动态规划题

• 坐标型动态规划
• 序列型动态规划
• 划分型动态规划
• 区间型动态规划
• 背包型动态规划
• 最长序列型动态规划
• 博弈型动态规划

例题

序列型动态规划

…

划分型动态规划

Decode Ways

• 确定状态

  • 最后一步：最后一个字母，在数字序列中可以有N-1或N-1与N-2
  • 子问题：
    • 求数字串前N个字符的解密方式数，即需要知道数字串前N-1和N-2个字符的解密方式数；
  • 状态：设数字串S前i个数字解密成字母串有**f[i]**种方式。

• 转移方程
  $$
  f[i] = f[i-1]|S[i-1]对应一个字母 + f[i-2]|S[i-2]S[i-1]对应一个字母
  $$

• 初始条件和边界情况

  • 初始条件：f[0] = 1，即空串有1种方式解密
    • 解密成空串
  • 边界情况，若i=1，则只有一个数字

• 计算顺序

  • f[0]，f[1]，f[2]，…，f[N]

坐标型动态规划