动态规划概念和基础线性DP

  |  

摘要: 动态规划的基本概念

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们系统学习一下动态规划中一些基本概念。这里我们参考《算法竞赛进阶指南》中关于动态规划的讲解,把动态规划的几个核心概念梳理一下,并做一个总结。

本文涉及到的概念可以在以下思维导图查看:

动态规划用一句话概括就是对各个状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。


$1 动态规划基础概念

(1) 阶段 (子问题)

动态规划把原问题视为若干个重叠子问题的逐层递进,每个子问题的求解过程都构成一个阶段。在完成前一个阶段的计算后,才会执行下一阶段的计算。

(2) 无后效性

【在完成前一个阶段的计算后,才会执行下一阶段的计算】

无后效性: 为了保证这些计算能够按顺序,不重复地进行,DP 要求已经求解的子问题不受后续阶段的影响。(后面的阶段对前面的阶段没有影响)

(3) 状态,转移,决策 (DAG)

由无后效性。DP 对状态空间的遍历构成 DAG,遍历顺序就是该 DAG 的一个拓扑序。DAG 中的节点对应问题的状态,边对应状态之间的转移,转移的选取是 DP 中的决策

(4) 最优子结构,重复子问题

最优子结构: 当动态规划用于求解最优化的问题时,下一阶段的最优解应该能由前面各阶段子问题的最优解导出

在阶段计算完成的时候,只会在每个状态上保留与最终解集相关的代表信息,这些信息具有可重复的求解过程,并且能够导出后续阶段的代表信息。

总结

状态,阶段,决策是动态规划算法的三要素。

无后效性,最优子结构,重复子问题是问题能用 DP 求解的三个基本条件。

$2 阶段的推导

动态规划是对各维状态进行分阶段,有顺序,无重复,决策性的遍历求解,其中对阶段进行划分后,每个阶段就是一个子问题。

动态规划算法有不同的阶段划分和推导的方式,常见的阶段划分方式如下:

  • 线性DP: 具有线性阶段划分的 DP 问题。
  • 树形DP: 以节点的深度作为阶段的 DP 问题。
  • 图上DP: 以节点在图上的拓扑序作为阶段的 DP 问题。

线性DP

线性DP : 具有线性阶段划分的 DP 问题。

这是一个广义的概念,与线性空间类似,如果一个 DP 算法的状态包含多个维度,但是各个维度上具有线性变化的阶段,也是线性DP,例如背包问题,区间DP 均属于这种情况。

线性DP中最常见的几种中阶段划分

(1) 单串阶段划分

代表问题:最长上升子序列。

状态表示dp[i] := 以 s[i] 结尾的最长上升子序列长度

阶段划分:子序列的结尾位置,从前到后。

参考:最长上升子序列LIS

(2) 双串阶段划分

代表问题:最长公共子序列。

状态表示dp[i][j] := s[0..i], t[0..j] 的最长公共子序列长度

阶段划分:s 和 t 分别已经处理的长度,二维。

参考:最长公共子序列LCS

(3) 棋盘阶段划分

代表问题:数字三角形。

状态表示dp[i][j] := 从 (0, 0) 走到 (i, j) 的最大的和

阶段划分:路径的结尾位置(矩阵中的行列位置),二维。

参考:棋盘DP

树形DP

以节点的深度作为 DP 的阶段。

参考:树形DP

图上DP

以节点在图上的拓扑序作为 DP 的阶段。

参考:DAG上的DP


$3 状态转移方程

状态转移方程一般可以有两种思考方式:

  1. 当前状态可以从哪些状态转移过来。
  2. 当前状态可以转移到哪些状态。

Share