Dynamic Progamming

动态规划的实质: 避免重复的中间结果计算

递归与动归的区别与联系：DP解决了重复计算的问题

DP的两种实现方法:

  • 记忆化搜索: 从大到小搜索
    • 画搜索树
    • 万金油
  • 多重循环: 从小到大搜索

多重循环：

  • 自底向上，自终点至起点的方法
  • 自顶向下，自起点至终点的方法

多重循环DP遇到的困难：

  • 循环不能解决问题
  • 初始状态找不到

什么时候使用记忆化搜索

  • 状态转移特别麻烦，不是顺序性
    • Longest Increasing continuous Subsequence 2D
      • 遍历x,y 上下左右四个格子 dp[x][y] = dp[nx][ny]
    • Coins in a Line III
      • dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1]);
  • 初始化状态不是很容易找到
    • Stone Game
      • 初始化dp[i][i] = 0
    • Longest Increasing continuous Subsequence 2D
    • 初始化极小值
  • 从大到小

DP两种方式比较 for循环

  • 空间优化
  • 时间优化
  • 从左到右
  • 背包

记忆化搜索

  • 简单
  • 由大到小
  • 初始化状态不易找到
  • 非顺序性

Rolling Array滚动数组：动态规划 优化存储空间

使用滚动数组

  • 状态 State
    • f[i][j] 表示以i和j作为正方形右下角可以拓展的最大边长
  • 方程 Function
    • if matrix[i][j] == 1 f[i%2][j] = min(f[(i - 1)%2][j], f[i%2][j-1], f[(i-1)%2][j-1]) + 1;、
    • if matrix[i][j] == 0 f[i%2][j] = 0
  • 初始化 Intialization
    • f[i%2][0] = matrix[i%2][0];
    • f[0][j] = matrix[0][j];
  • 答案 Answer
    • max{f[i%2][j]}

这类题目特点

  • f[i][j] = 由f[i-1]行 来决定状态，
  • 第i行跟 i-1行之前毫无关系，
  • 所以状态转变为 f[i%2][j] = 由f[(i-1)%2]行来决定状态

什么时候使用动态规划 满足下面三个条件之一：

  • 最优：求最大值最小值
  • 可行：判断是否可行
  • 方案数：统计方案个数

则 极有可能 是使用动态规划求解

什么时候不适合使用动态规划

  • 求出所有 具体 的方案而非方案个数
  • 输入数据是一个 集合 而不是 序列
  • 暴力算法的复杂度已经是多项式级别：动态规划擅长与优化指数级别复杂度(2^n,n!)到多项式级别复杂度(n^2,n^3)，不擅长优化n^3到n^2

则 极不可能 使用动态规划求解

动归的四要素：

  • 状态 State：灵感，创造力，存储小规模问题的结果
  • 方程 Function：状态之间的联系，怎么通过小的状态，来算大的状态
  • 初始化 Initialization：最极限的小状态是什么, 起点
  • 答案 Answer：最大的那个状态是什么，终点

动态规划分类：

  • 坐标型
  • 序列型
  • 双序列
  • 划分型（博弈类）
  • 区间型
  • 背包型

坐标型动态规划(1D, 2D, 3D...)

  • state:
    • f[x] 表示我从起点走到坐标x…… (第x位置)
    • f[x][y] 表示我从起点走到坐标x,y…… 向右向下走, 如果四个方向都可以走的话那就要试图找到另外一条线索可以限定走的方向，否则不能用DP
  • function: 研究走到x,y这个点之前的一步
  • initialize: 起点
  • answer: 终点

初始化一个二维动态规划时就去初始化第0行和第0列

单序列动态规划

  • state: f[i]表示前i个位置/数字/字符，prefix前缀
  • function: f[i]=f[j]… j是i之前的一个位置
  • initialize: f[0]
  • answer: f[n] 一般answer是f(n)而不是f(n-1), 因为对于n个字符，包含前0个字符（空串），前1个字符...前n个字符

如果不是跟坐标相关的动态规划，一般有n个字符/数字，就开n+1个位置的数组，第0个位置单独留出来做初始化

双序列动态规划

给出两个序列

  • state: f(i)(j)代表了第一个sequence的前i个字符/数字，配上第二个sequence的前j个字符/数字
  • function: f(i)(j)=研究第一个序列第i个和第二个序列第j个的匹配关系
  • initialize: f[i][0] 和 f[0][j]
  • answer: f[n][m], n=s1的长度，m=s2的长度

博弈类DP

画搜索树 博弈有先后手

  • State: 定义一个人的状态
  • Function: 考虑两个人的状态做状态更新
  • Intialize:
  • Answer:

先思考最小状态

然后思考大的状态-> 往小的递推，那么非常适合记忆化搜索

区间类DP

  • 求一段区间的解max/min/count
  • 转移方程通过区间更新
  • 从大到小的更新
  • 这种题目共性就是区间最后求[0,n-1] 这样一个区间
  • 逆向思维分析 从大到小就能迎刃而解
  • 逆向=》 分治类似

背包类DP

  • 用值作为DP维度
  • DP过程就是填写矩阵
  • 可以使用滚动数组优化

注意DP数组每个维度要多加一个，因为需要(0，0)

坐标型动态规划题目

results matching ""

    No results matching ""