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

字数统计: 1.6k字 | 阅读时长: 5分

2020-11-09

动态规划100

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

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

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

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

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

$1 动态规划基础概念

状态空间遍历形成的 DAG

(1) 阶段 (子问题)

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

(2) 无后效性

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

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

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

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

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

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

在阶段计算完成的时候，只会在每个状态上保留与最终解集相关的代表信息，这些信息具有可重复的求解过程，并且能够导出后续阶段的代表信息。这样，动态规划对状态的抽象和子问题的重叠递进共同起到优化作用。

(5) 状态转移方程

动态规划算法把相同的计算过程作用于各阶段的同类子问题，我们一般只需要定义出 DP 的计算过程即可，这个计算过程称为状态转移方程。

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

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

总结

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

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

对具体问题，可以按以下流程分析，难点在于如何把问题形式化为状态空间，进一步抽象出 DP 的状态表示和阶段划分：

找到重复子问题，最优子结构；
根据子问题的求解过程明确阶段划分；
根据由上一阶段的结果计算当前阶段时所需的信息，抽象出状态表示，如果阶段不足以表示一个状态，需要把附加信息也作为状态的维度；
由子问题的重叠递进的方式，设计状态转移方程，并给出边界，目标；

经过以上分析后，最终算法呈现出来的事状态设计、边界值、目标、状态转移方程四部分。其中状态设计中除了划分阶段的维度，还可能有附加信息的维度。

给出了状态转移的方程、边界和目标，一个动态规划的问题就算是解决了，程序实现可能会有些细节，但是是小问题。

$2 阶段的划分方式

动态规划是对各维状态进行分阶段，有顺序，无重复，决策性的遍历求解，

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

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

线性DP

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

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

(1) 单串阶段划分

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

状态表示：$dp[i]$ 表示 $a[0..i]$ 上以 $a[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 的阶段。阶段之间以拓扑序进行推导。