DP 的本质

一般 DP 的本质

• 状态：点。（带了值）
• 转移：边。
• DP：在 DAG 上推。（得到 / 更新 点的值）

特殊（类似 DP）

图不是 DAG。有两种思路：

• 解方程
  • 简单的：直接解（比如只有一个环）。
  • 复杂的：高斯消元。
    • 高斯消元。
    • 高斯-约旦消元。
• 图论
  • 类似最短路：
    • Dijkstra 算法 / 类似 Dijkstra 的算法。
    • SPFA 算法 / 类似 SPFA 的算法。
  • 其他的我可能还不知道。

DP 的要素

（我目前想起来的。）

• 状态。无后效性，设计方式：把之后要用的全部塞进状态里。
• 转移方程。就近转移，不重不漏。最值（min、max）、其他运算。
• 初值。按定义 / 为了转移后得到的状态的值正确。[也许要为了之后正确用奇怪的定义。]（？）（好像是 重返现世 那题）。[注意特殊情况。]（之前写的，现在不知道例子是什么）
• 最终答案。可能是一个状态，可能是多个状态运算起来。

可能一般按 状态 -> 转移方程 -> 初值、最终答案 的顺序思考。

DP 的转移方式

之前听说叫“填表法”和“刷表法”。

推到其他状态

在当前状态上做改动。个人认为更符合正向思维。

似乎转移对应关系复杂的时候用这种方式比较清晰方便。

从其他状态转移来

找之前的状态。个人认为更符合逆向思维。

似乎更常用。

似乎在决策方面优化 DP 的时候常用。比如 单调栈、单调队列、斜率、决策单调性、线段树之类的 DS 大力找决策点 优化 DP。

DP 的转移顺序

按拓扑序

（我知识水平非常有限，不太了解拓扑序，这里说拓扑序可能不止一种是不严谨的或错误的，但是就是这个意思 qwq。）

一般的转移顺序。本质上是按照 DAG 的拓扑序。

注意拓扑序可能不止一种，有时换一种顺序可能可以优化 DP，换顺序如：二维状态的 DP，先枚举哪一维后枚举哪一维可能可以颠倒。（如：把序列分割成给定个数个区间的题。）

记忆化搜索

避免了转移顺序的问题。

注意初始化 \(vis\) 数组（或者直接把 \(f\) 初始化成 \(-1\) 之类的）。

时间复杂度[一般要]（？）结合状态数来分析，但不一定等于状态数，可能还要算上转移和其他的代价。（如二维区间 DP。）

典型例子是数位 DP、二维区间 DP。