算法-动态规划初步

4FGR2025-04-142025-05-21

参考资料：动态规划基础 - OI Wiki

目前绝大多数内容摘自OI-Wiki,个人理解重构等后续更新

动态规划初步

动态规划(Dynamic Programming)，简称DP，它本身不是一种特定的算法，而是一种思想。当状态变动与之前或之后状态有关时，我们往往可以使用方程来描述这种关系。这种方程被称作状态转移方程。

动态规划原理

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

最优子结构

具有最优子结构也可能是用适合贪心的方法求解。

注意要确保我们考察了最优解中用到的所有子问题

证明问题最优解的第一个组成部分是做出一个选择;
对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解，你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
证明作为构成原问题最优解的组成部分，每个子问题的解就是它本省的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题中的解用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

原问题的最优解中涉及多少个子问题。
确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个顶点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

无后效性

已经求解的子问题，不会再受到后续决策的影响。

子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征(称之为状态);
寻找每一个状态的可能决策，或者说是各状态间的相互转移方式(用数学的语言描述就是状态转移方程)。
按顺序求解每一个阶段的问题。

如果用图论的思想理解，我们建立一个有向无环图，每个状态对应图上一个节点，决策对应节点键的连边。这样问题就转变为了一个再DAG上寻找最长(短)路的问题。

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

在求解动态规划的问题时，记忆化搜索与递推的代码，在形式上是高度类似的。这是由于它们使用了相同的状态表示方法和类似的状态转移。两种实现的时间复杂度是一样的，只不过是将递推的形式转换成了递归的形式。

与递推相比，记忆化搜索因为不用明确规定访问顺序，在实现难度上有时低于递推，且能比较方便低处理边界情况。但与此同时，记忆化搜索难以使用滚动数组等优化，且由于存在递归，运行效率和低于递推。

写记忆化搜索的方法：

方法一

把这道题的 $dp$ 状态和方程写出来
根据它们写出 $dfs$ 函数
添加记忆化数组

方法二

写出这道题的暴力搜索程序(最好是 $dfs$)
将这个 $dfs$ 改成「无需外部变量」的 $dfs$
添加记忆化数组

最长公共子序列

最长公共子序列问题

给定一个长度为 n 的序列 A 和一个长度为 m 的序列 B（n, m ≤ 5000），求出一个最长的序列，使得该序列既是 A 的子序列，也是B的子序列。

设 $f(i,j)$ 表示只考虑 $A$ 的前 $i$ 个元素, $B$ 的前 $j$ 个元素时的最长公共子序列的长度，求这时的最长公共子序列的长度就是子问题， $f(i,j)$ 就是我们所说的状态，则$f(n,m)$ 是最总要达到的状态，即所求结果。

对于每个$f(i,j)$ 存在三种决策: 如果$A_i=B_j$ ,就可将它接到公共子序列的末尾；另外两种决策分别是跳过 $A_i$ 或者 $B_j$ 。状态转移方程如下： \[ f(i,j) = \begin{cases} f(i-1,j-1)+1, &A_i = B_j\\ \max(f(i-1,j),f(i,j-1)), &A_i \neq B_j \end{cases} \] 该做法的实践复杂度为 $O(nm)$

另外，本题存在$O(\frac{nm}{w})$ 的算法。有兴趣的同学可以自行探索。

int a[MAXN],b[MAXM],f(MAXM)[MAXM];

int dp(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<m;j++){
            if(a[i] == b[j])
                f[i][j] = f[i-1][j-1]+1;
            else
                f[i][j] = max(f[i-1][j],f[i][j-1]);
		}
    }
    return f[n][m];
}

最长不下降子序列

给定一个长度为n的序列A(n<=5000), 求出一个最长的A的子序列，满足该子序列的后一个元素不小于前一个元素

算法一

设 $f(i)$ 表示以 $ A_{i} $ 为结尾的最长不下降子序列的长度，则所求为 $ max_{1\leq{j}\leq{i}, A_j\leq{A_i}}(f(j)+1) $

容易发现该算法的时间复杂度为 $O(n^2)$

int a[MAXN],d[MAXN];

int dp(){
    d[1] = 1;
    int ans = 1;
    for(int i=2; i<=n; i++){
        d[i] = 1;
        for(int j=1; j<i; j++){
            if(a[j] <= a[i]){
                d[i] = max(d[i],d[j]+1);
                ans = max(ans,d[i]);
            }
        }
	}
    return ans;
}

算法二

当 $n$ 的范围扩大到 $n\leq10^5$ 时，第一种做法就不够快了, 下面给出了一个 $O(n\log n)$ 的做法。

回顾一下之前的状态: $(i,j)$。

但这次, 我们不是要按照相同的 $i$ 处理状态，而是直接判断合法的 $(i,j)$ 。

再看一下之前的转移: ${(j,l-1)}\rightarrow{(i,j)}$ ,就可以判断某个 $(i,j)$ 是否合法。

初始时 $(1,1)$ 肯定合法。

那么，只需要找到一个 $l$ 最大合法的 $(i,j)$ ，就可以得到最终最长不下降子序列的长度了。

那么，根据上面的方法，我们就需要维护一个可能的转移列表，并逐个处理转移。

所以可以定义$a_1···a_n$ 为原始序列，$d_i$ 为所有长度为i的不下降序列的末尾元素的最小值，$len$ 为子序列的长度。

初始化：$d_1 = a_1$ $len=1$ 。

现在我们已知最长的不下降子序列长度为1，那么我们让 $i$ 从$2$ 到 $n$ 循环，依次求出前 $i$ 个元素的最长不下降子序列的长度，循环的时候我们只需要维护好 $d$ 这个数组还有 $len$ 就可以了，关键在于如何维护。

考虑进来一个元素 $a_i$ :

元素大于等于 $d_{len}$ ，直接将该元素插入到 $d$ 序列的末尾。
元素小于 $d_{len}$ ，找到第一个大于它的元素, 用 $a_i$ 替换它。

为什么:

对于步骤1：

由于我们是从前往后扫，所以说元素大于等于 $d_{len}$ 时一定会有一个不下降子序列使得这个不下降子序列的末项后面可以再接这个元素。
对于步骤2：

同步骤1，如果插在 $d$ 的末尾，那么由于前面的元素大于要插入的元素，所以不符合 $d$ 的定义，因此必须先找到第一个大于它的元素，再用 $a_i$ 替换。

步骤2如果用暴力查找，则时间复杂度仍然是 $O(n^2)$ 的。但是根据 $d$ 数组的定义, d一定是单调不减的，因此可以采用二分查找将时间复杂度降至 $O(n\log n)$ 。

for(int i=0; i<n; i++) cin >> a[i];
memset(dp,ox1f,sizeof dp); //初始化dp很大
mx = dp[0];
for(int i= 0; i< n; i++){
    //寻找第一个大于a[i]的元素的位置
    *std::upper_bound(dp, dp+n,a[i]) = a[i];
}
ans = 0;
while(dp[ans]!=mx) ++ans;
return ans;
/*
每次寻找第一个大于a[i]元素的位置，并将其赋值为a[i]，即便顺序是不对的，但实际上保留了最长不下降子序列的最大长度 我们假设我们更新了a[i](占据了之前a[0···i-1]的某一个位置)，当我们判断a[i+1]时，它如果刚好小于a[i]的后面的某个元素，那么就插在那个元素的位置，与a[i+1]同理，如果它大于d[len-1],就说明其延长了len，结果是无视之前a[i]插入的影响的。
*/