前言

这几天做dp题，发现有一些基础的dp模型还没有完全理解。遂查阅相关博客和课程，刚好在YouTube上看到了MIT6.006的课程，课上老师提出了一个框架SRTBOT，通过 $6$ 个步骤来解析动态规划相关的问题，受益匪浅。所以做一个记录总结。

关于相关的网课资源，可以在CS自学指南找到。

Part.0 什么是SRTBOT框架

SRTBOT框架即通过 $6$ 个步骤来实现将一个问题分解为多个子问题，且这些子问题之间存在一定的拓扑关系，并最终能够通过合并子问题来解决原始问题。具体的步骤为：

Subproblems definition
定义子问题
Relate subproblem solutions recursively
递归关联子问题
Topological order to argue relation is acyclic and subproblems form a DAG
根据拓扑排序确定解决子问题的顺序
Base cases
边界情况
Original problem
原始问题
Time analysis
时间复杂度

定义子问题（Subproblems definition）

对于原始问题，我们可以将其视为一个带参数的问题；那么，我们可以通过定义子问题，将原始问题分解为多个规模更小、参数不同的子问题。

在设计子问题的时候，我们可以根据输入的子集来定义子问题。

举个例子，在求解LIS问题时，题目给出的是一个序列，那么可以定义子问题为以 $i$ 结尾的LIS长度，最后我们只需要取所有子问题的最大值即可。

通常情况下，我们通过将子问题转化为一个函数，通过更改函数的参数，来表示不同的子问题。在动态规划中，我们将其称为状态。

还是用LIS来举例，可以定义状态为 $dp(i)$ 表示以 $i$ 结尾的LIS长度。

此外，状态的定义还需要考虑到问题的约束条件，或者对子问题进行扩展。这也是最常见的DP类型。

例如，在没有上司的舞会中，我们可以定义状态为 $dp(i, 0/1)$ 表示以 $i$ 为根的子树中，$i$ 不选/选的最大快乐值。这里的状态就包含了问题的约束条件，即 $i$ 不能同时选和不选。

我们可以发现，定义子问题的时候，不需要考虑怎么计算子问题的答案，只需要考虑子问题的状态即可。

递归式关联子问题（Relate subproblem solutions recursively）

在定义子问题之后，我们需要考虑如何通过子问题的状态来递归地关联子问题。

这一步通常是动态规划的核心部分，我们需要找到子问题之间的关系，并通过这些关系来计算子问题的答案。

继续以LIS为例，我们可以发现，以 $i$ 结尾的LIS长度，可以通过遍历 $j < i$ 的所有位置，找到满足 $a_j < a_i$ 的位置，然后取这些位置的LIS长度的最大值加一。

那么，我们可以得到递归式：

$$ dp(i) = \max_{j < i, a_j < a_i} {dp(j) + 1} $$

在这个问题中，对于一个更大的问题，我们可以将其分解为更小的子问题，并根据不同的决策，利用 局部暴力枚举 来关联多个子问题。

显然，我们可以发现，通过多次的决策和枚举，我们可以从子问题递归地关联出更大的问题。直至解决原始问题。

根据拓扑排序确定解决子问题的顺序（Topological order to argue relation is acyclic and subproblems form a DAG）

根据前面的递推式，我们可以将所有的子问题关联起来，将子问题看作图中的一个顶点，根据递推式用有向边连接这些顶点。最后，就会构成一个有向无环图（DAG）。

为什么最终会构成DAG？

由于我们一定是自下而上的解决子问题，那么对于一个子问题而言，在到达此顶点的时候，其依赖的所有子问题都已经被解决了。这样就可以保证在解决问题时，不会出现环。

所以，我们需要创建一个表格或者数组，用于存储子问题的答案，这样在需要的时候，就可以直接从表格中获取答案，而不需要重新计算。也就是 记忆化搜索。

本质上，所有的动态规划问题，都是一个 递归问题，只是在递归的过程中，我们需要记录已经计算过的子问题的答案，避免重复计算。

边界情况（Base cases）

对于递归问题，一定会存在一个边界，也就是最小的独立子问题，也是最简单的子问题，可以直接求解，无需进一步分解子问题。

原始问题（Original problem）

通过解决所有的子问题来解决原始问题。

一般而言，原始问题也是一个子问题，只是其参数是完整的输入。所以答案会形如 $dp(n)$。

当然也会有例外，依然是LIS问题。在LIS问题中，原始问题是求整个序列的LIS长度，那么我们可以定义状态为 $dp(i)$ 表示以 $i$ 结尾的LIS长度，最后答案就是 $\max_{1 \leq i \leq n} {dp(i)}$。

时间复杂度分析（Time analysis）

在动态规划中，时间复杂度通常是子问题的数量乘以每个子问题的时间复杂度。

Part.1 通过解决子问题实现的相关算法和数据结构。

SRTBOI框架不止适用于动态规划，其背后的本质思想，即 通过解决子问题来解决原始问题 也是很多数据结构的思想。例如：分治、二分、线段树等等。

Part.1.1 动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。同时，其满足最优子结构、无后效性和子问题重叠的性质。

由于其有大量的重叠子问题，我们可以采用记忆化，将子问题的结果存储起来，避免重复计算。由于这个性质，大部分动态规划问题都可以在线性的时间复杂度内解决问题。

Part.1.2 分治

分治是一种将一个复杂的问题分解为两个或更多的相似子问题，直到子问题足够简单，可以直接解决的方法。然后将子问题的解合并，得到原问题的解。

分治与动态规划的区别在于，分治大多是将问题分解为多个独立的子问题，而动态规划将问题分解为多个重叠的子问题。

Part.1.3 二分

二分是一种通过将问题的解空间不断缩小来找到问题解的方法。其本质上也是一种分治思想。

由于每次操作都会将问题的解空间缩小一半，所以二分的时间复杂度是 $O(\log n)$。

Part.1.4 线段树

线段树是一种用于存储区间信息的数据结构。其本质上也是一种分治思想。

线段树通过将区间不断分解为多个子区间，来维护区间的信息。每个节点表示一个区间，节点的子节点表示该区间的子区间。之后，通过多种操作（如查询、修改），可以在 $O(\log n)$ 的时间复杂度内完成。

Part.2 SRTBOT在动态规划中的应用

通过SRTBOT框架，我们可以更好地理解动态规划问题的本质，并且能够更系统地解决动态规划问题。

下面通过一个例子来说明SRTBOT框架在动态规划中的应用。

例题：最长上升子序列（LIS）

给定一个长度为 $n$ 的序列，求该序列的最长上升子序列的长度。

Step 1: 定义子问题

我们可以定义子问题为 $dp(i)$ 表示以 $i$ 结尾的LIS长度。

Step 2: 递归关联子问题

根据LIS的定义，我们可以得到递归式：

$$ dp(i) = \max_{j < i, a_j < a_i} {dp(j) + 1} $$

其中，$a_i$ 表示序列中的第 $i$ 个元素。

Step 3: 拓扑排序确定解决子问题的顺序

由于 $dp(i)$ 依赖于 $dp(j)$，其中 $j < i$，所以我们可以按照从小到大的顺序解决子问题。

Step 4: 边界情况

对于边界情况，我们可以定义 $dp(1) = 1$，因为以第一个元素结尾的LIS长度为 $1$。

Step 5: 原始问题

最后，我们需要求解原始问题，即整个序列的LIS长度。答案为：

$$ \max_{1 \leq i \leq n} {dp(i)} $$

Step 6: 时间复杂度分析

由于我们需要计算 $n$ 个子问题，每个子问题需要遍历前面的 $i-1$ 个元素，所以时间复杂度为 $O(n^2)$。

当然，我们也可以通过优化，将时间复杂度降低到 $O(n \log n)$，具体做法可以参考最长不下降子序列。

参考上面的示例，我们可以发现，通过SRTBOT框架，可以很方便的分析动态规划问题。但要注意，做题的时候，不能死板的只考虑SRTBOT框架，而要根据具体问题，灵活地调整框架。SRTBOT告诉我们的更多是一种解决问题的思路，而不是一种固定的模板。