dp 基础
本文默认读者接触过基本的 dp 思想。
大约是对 dp 的一个重新解构，因为近期发现自己对“概念”的理解真的很不深入。
同样的，本博客的 dp 部分也会在近期重构。
动态规划可以看作，在所有状态构成的状态空间中，建立了一张 DAG（有向无环图）。
DAG 保证无环，也就是保证了 dp 的无后效性，决策/转移则是这张 DAG 上的边。
而状态本身，是 DAG 上的节点，它们代表的不仅仅是某一个情况，而是以它结尾的多条转移链对应的最优解，这多条转移链构成的子图被称作一个问题。
阶段是由同层（你可以理解为 bfs 时深度相同）的节点构成的，它的意义是对原问题的子问题进行划分，方便求解。
最优子结构是应用动态规划的大前提，它的内容是，一个问题的最优解，应当由它的子问题的最优解导出，换句话说，它给转移和状态加上了束缚，使得它们能够正确转移。
我时常分不清楚贪心和 dp 的区别，因为它们能解决的问题同样都应该拥有最优子结构。
不过现在看来，正是这个共同点成为了找到它们不同点的关键，注意到上面粗体高亮的“多条”了吗？
区别就在于此，贪心的子问题永远是链，dp 的子问题是子图，复杂程度不严格大于贪心，可以看两张图来得到更形象的理解：
这是贪心的转移图：
这是 dp 的转移图：
为了有更形象的理解，举几个简单的例子：
- 数字三角形：
- 设 \(dp(i, j)\) 表示从 \((1, 1)\) 走到 \((i, j)\)，可以获得的最大价值。
- 这个的阶段应当是行，这是显然的，如果选择列的话，就没有办法覆盖整个状态空间了。
- 转移是考虑从 \(dp(i - 1, j)\) 和 \(dp(i - 1, j - 1)\) 转移过来，加上 \((i, j)\) 的权值就行了。
- 这告诉我们，在满足最优子结构性质的前提下，我们转移只需要关心当前阶段的情况就行了，之前阶段，或者进一步说，之前的子问题的最优解，都已经被包含在了 dp 状态本身里了。
- Longest Increasing Subsequence：
- 设 \(dp(i)\) 表示考虑前 \(i\) 个位置，以 \(i\) 结尾的 IS 的最大长度。
- 转移是考虑从所有的 \(j\text{ s.t. }a_j < a_i\) 的 \(dp(j)\) 转移过来，这里就是一个“约束”，用来确定哪些状态是合法的，可以正确转移过来的。
- 这是一个线性序列上的 dp，阶段直接就是下标，或者说我们的子问题是考虑了一段前缀的。
- 阶段通常需要具有一些特殊的性质来支撑它作为阶段。
- 比如说，一个位置的答案依赖它之前的位置的答案，那么我们就可以以位置为阶段，每次考虑一段前缀，这就是线性 dp 了。
- 或者说，一个节点的答案依赖于子树的信息，那么我们就以子树为阶段，每次考虑一个子树，这就是树形 dp 了。
- 又有些时候，出于方便考虑，我们直接对答案的数位进行考虑，不关心做贡献的树具体是多少，只关心这一位的贡献，这就是数位 dp 了。
- Longest Common Subsequence
- 设 \(dp(i, j)\) 表示 \(a[1..i],b[1..j]\) 的 CS 的最大长度。
- 转移需要考虑多种情况，一种是 \(a[i] = b[j]\)，另外一种是不等。
- 换句话说，一个阶段中的状态可能有不同的分类，为了覆盖完整个状态空间，我们需要转移全。
- 这里是最优化问题，所以直接转移就行了，只需要考虑不漏。
- 如果是计数问题，那么就需要考虑是否会重复，这就要求一种合法的基本情况和一个合法的转移序列是唯一对应的，这样，我们处理的信息天然就满足不重不漏性质，只需要保证转移合法，就能覆盖整个状态空间。
- Random Walk:
- 一个 bot，每次可以往八连通的格子里走，初始在一个位置，问走出网格的期望。
- 这种期望相关的 dp 的一大特征就是，转移很容易成环，因为 bot 可以不停转圈，但是这样的状态仍然合法。
- 我们先不管这么多，对每个位置把转移方程列出来，显然会成环对吧。
- 这个时候，把所有的转移方程当成一个线性方程组，用高斯消元就可以做了。
我之前考虑 dp 的时常会犯一个错误，一直不知道该怎么描述，现在发现其实是对最优子结构理解不清晰导致的：
比如说，没想清楚这个问题是否具有最优子结构，或者是对着一个没有最优子结构的信息做 dp。
举个例子，哎呦似乎有点难举出来，之后如果再遇到就写（希望不要遇到了）
但是教训是，可以尝试假设它有最优子结构，然后反证（证明比举反例好，反例容易想错）。
精简一点，dp 只需要考虑这几个问题：
- 阶段是？状态是？
- 咋转移？不重不漏了吗？
- 最后的就是考虑优化了，这部分可以参见本目录下的“dp 优化”。
最后更新:
July 22, 2023