动态规划概念和基础线性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. 当前状态可以转移到哪些状态。

---