DP-学习笔记(基础篇)

· · 个人记录

DP 的引入

  1. \texttt{P1255 数楼梯}
#include<bits/stdc++.h>
using namespace std;

int lf[5005][5005];
int len=1;
void pls(int x)
{
    for(int i=1;i<=len;i++) lf[x][i]=lf[x-1][i]+lf[x-2][i];
    for(int i=1;i<=len;i++) if(lf[x][i]>9){
            lf[x][i+1]+=lf[x][i]/10;lf[x][i]%=10;
        }
    if(lf[x][len+1]) len++;
}
int main()
{
    int n;
    cin>>n;
    lf[1][1]=1;
    lf[2][1]=2;
    for(int i=3;i<=n;i++) pls(i);
    for(int i=len;i>0;i--)cout<<lf[n][i];

    return 0;
}

DP 的意义

由上题，我们发现每次求方案时总会碰到同样的情况，由此，直接搜索即可。

于是我们想到可以用东西把它这个东西记录下来，这样在求第一遍的时候需要求，在求第二遍的时候就可以直接用上次求的答案，大大优化了时间复杂度。

DP 的要求

DP 对时间复杂度的优化很大，但不是每个算法都可以用 DP 优化。

使用 DP 须满足以下要求：

  1. 问题都可以分拆成子问题解决。比如说上面提到的台阶问题，在解决问题 n 的时候，我们把它分拆 成了两个一模一样的子问题 n-1, n-2 来解决。

  2. 无后效性。意思就是，我现在设的状态的转移策略以及求解，对之后的状态的转移策略以及求解没 有影响，这样的话现在做的策略就不需要考虑之后的其他东西。

  3. 重叠子问题。很简单，意思就是有多个完全一样的东西要解决。既然完全一样，那我们只要求一次了。

  4. 最优子结构。也就是说子问题的最优解可以拼成整个问题的最优解。例如要求长沙到北京，且途径上海的最短路程，那么先求长沙到上海的最短路程，再求上海到北京的最短路程，然后拼起来就可以了。

DP 与贪心的联系与区别

以上看来， DP 和贪心的要求十分相似。

它们都是通过求解子问题来解决整个问题（最优子结构），且当前的抉择都不能对之后造成影响（无后效性）。

但一些题目只能用 DP 不能用贪心做，为什么？

以 \texttt{P1164 小A点菜(0-1 背包)} 为例，

如果直接贪心是有后效性的，因为现在的选择会对剩余背包的容量造成影响，但是如果我们 DP，设 f[i][j] 表示前 i 个物品，已经填了体积 j 的最优解，那么这个问题就可以解决了。

#include<iostream>
using namespace std;
const int lf=(333&21)<<7;
int n,m;
int a[213];
int dp[lf];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            dp[j]=dp[j-a[i]]+dp[j];
        }
    }
    cout<<dp[m];
    return 0;
}

DP 的状态

状态常用 f[i][j][\ldots] 表示。这里的 i,j\ldots 是状态每个维度描述的特征量，用于描述某些特征，维度数量可以根据需求确定，但是确定后必须保持不变。状态 f[i][j][\ldots] 本身会存储一个量，其常常是对应问题的解。

状态的本质是，将具有共同特征的方案（通常是解决同一个问题）合并到一起来处理，而非暴力地挨个处理每一个方案。

状态存储的，通常是有后效性的特征。回到上述问题，为什么用 DP 可以求解而贪心不行? 因为直接贪心是有后效性的，每个选择会让背包的空闲变少，但是在 DP 中，我们把这个有后效性的量存储到了状态中，即设 f[i][j] 表示前 i 个物品，总体积为 j 的最优解。这样，在状态与状态之间就没有后效性了。

一般来说，我们都会把有后效性的量存储在状态中。

DP 的转移与边界

在状态之间的转移，一般来说，我们是找到一种把当前问题变成子问题的方式，然后用子问题的答案去更新当前问题。比如说当前问题是 A，子问题的集合是 S，那么 f[A] = \operatorname{Option}\{ f[B] \} (B \in S)，其中 \operatorname{Option} 是某种操作。

那如果一个问题它没有子问题呢？ 这样的话它就是一个严格边界。这个问题不能通过任何的转移得到答案，我们只能人工给它赋值。比如说在前面的台阶问题中 f[1] 就是一个边界，因为我们走到台阶 1 之后就不能走了，所以就没有子问题了，这时候我们就需要人工给它赋值，在这里是 f[1]=1。

当然，我们也可以自己定义一些不严格的边界。所谓不严格，就是它可以通过转移得到，但是我们还是通过人工给它赋了正确的值，在台阶问题中，如果我们把 f[2]=1, f[3]=2 一开始就确定好，那么它们也是一个边界。

严格的边界是必须人工赋值的，不严格的边界可以不进行人工赋值，一般来说出现不严格的边界，要么是严格的边界不好找，就一股脑把可能是边界的状态都赋了值，要么是这些不严格的边界电脑算很慢，但是人工算很快，所以我们为了节省时间就这么干了。

DP 的转移方式

假设我们已经知道了 dp[i][j]=\max\{dp[i-1][j-1], dp[i-1][j], dp[i-1][j-1]\}，我们怎么实现转移呢？

  1. 填表法。看每个状态从哪里转移过来，即在枚举 i,j 的时候，用 dp[i][j]=max{dp[i-1][j-1], dp[i-1][j], dp[i-1][j-1]} 直接转移。

  2. 刷表法。每个状态去转移它可以转移的地方，即在枚举 i,j 的时候，使用 dp[i][j] 去更新 dp[i+1][j] , dp[i+1][j+1], dp[i][j+1] 的值

至于刷表法和填表法如何使用，那就见仁见智了。 一般来说，就是想到了哪种转移方式就用哪种，它们没有什么很大的区别。

DP 的求值策略

一般来说，在 DP 的时候我们都会使用循环，即枚举 i,j,k...，然后用 f[i][j][k][...] 去填表或者刷表。

但如果枚举的顺序不好定怎么办？

可以使用记忆化搜索。

记忆化搜索

我们定义个搜索函数 DP(int x, int y)，表示求 f[x][y] 的值。
也就是说，如果我们要求 f[x][y]，直接调用 DP(x,y)。

  • 如果 f[x][y] 还没有求过，就看 f[x][y] 怎么被转移过来。
  • 如果 f[x][y] 已经求过，就直接返回 f[x][y]。

不难发现的是，这样只能填表。

枚举递推和记忆化搜索这两种方法各有千秋。

DP 的难点

一般来说，DP 的难点是状态的设计和转移的设计。

一方面，我们可以积累状态设计的模型和转移设计的模型，以及它们的优化方法。

另一方面，我们需要提高自己的思维能力，让自己也能构造出一种新的 DP 状态和转移。

线性 DP

如定义所言，线性 DP 是线性的 DP。

什么是线性？
就是我们在一个或者多个序列上进行着 DP，其中状态的某些维度记录了在这些序列上的位置（一个序列对应一个位置），且转移的时候某个状态的转移依赖于前面的状态（举个例子，有一个序列，状态中某维 i 记录的是序列上的位置，枚举顺序是 i 从 1 到 n，那么在求 f[i] 的时候我们应该只依赖于 f[1]\sim f[i-1]）

可以发现边界状态就是转移方程中前面的状态没有的状态（用上面的例子就是 f[1]）

例 1：最长公共子序列

给出两个序列 A,B,|A|=N,|B|=M，求一个最长的序列 S，使得 S 既是 A 的子序列，又是 B 的子序列。

N,M \le 2000

样例输入 

5 5
1 4 6 3 5
4 6 1 5 6

样例输出 

3

解析

我们可能会先找一个相同的数字，然后往后继续找第二个相同的数字，以此类推。

这样一个 DP 就出来了！设 f[i][j] 表示最后匹配的数字是 a[i] 和 b[j]，我们就枚举上一个匹配的数字进行转移。

但是这样太慢了，为什么？
因为在上面的 DP 中有我们不需要知道的东西：最后一个匹配的数字是什么。而因为我们知道了这个东西，导致了每次转移要找上一个匹配的数字是什么。

如果设 f[i][j] 表示考虑第一个序列的前 i 个，第二个序列的前 j 个，得到的最长公共子序列长度。

转移就是 f[i][j] = \max\{f[i-1][j], f[i][j-1]\}，如果 a[i] 与 b[j] 相等，那么还可以从 f[i-1][j-1] + 1 转移过来。

我们虽然损失了上一个匹配的数字是什么的信息，但是我们这时候就不需要找上一个匹配的数字是什么了。也就是说我们舍弃一些无用信息，使得转移的时候我们不需要花时间去匹配这个信息。

例 2：\texttt{P1115 最大子段和}

例 3：\texttt{最长上升子序列}

区间 DP

如定义所言，区间 DP 就是区间上的 DP。

一般来说我们会设 f[l][r] 来存储的一个区间 [l,r] 的信息。

在转移的时候，一般是把小区间的信息，合并到一个大区间去。

例 1

你正在玩一个游戏，最开始，主持人给了你一个长度为 n 的序列 a，然后你每次可以取走序列的第一个数字或者最后一个数字，设你取的数字依次为 b[1], b[2], .., b[n]，那么你的得分为 \sum\limits^n_{i=1}b[i]^i。

你希望你的得分最大，忽略花在高精度上的时间。

n ≤ 2000, a[i] ≤ 10^9

样例输入 

4
1 4 2 3

样例输出 

274

Hint 1： 进行一些操作之后，剩下的数在原序列上的位置有什么性质？

Hint 2： 区间 DP。

解析

这个问题其实题面就已经告诉我们每次该怎么做了。

当游戏进行到 [l,r] 时，我们只有两种决策，一种是取 a[l]，一种是取 a[r]，此时问题变成两个子问题 [l+1,r] 和 [l,r-1] 。

所以设 f[l][r] 表示问题在区间 [l,r] 的答案，那么转移就是 f[l][r] = \max\{f[l+1][r] + a[l]^{n-(r-l)}, f[l][r-1] + a[r]^{n-(r-l)}\}

可以想想状态的边界是什么？

状态的边界是 l=r 的时候。

例 2：\texttt{P1880 石子合并}

总结

主要内容是 DP 的基础，以及线性 DP 与区间 DP 两个模型。

在设计状态的时候，我们常常会先手玩，然后把需要我们重复计算的东西给计入状态，上述几个问题都是从这里出发的。

但是我们不一定每次手玩都会采取方便 DP 的策略，所以我们需要通过目前算法存在的问题不断调整。比如说最大子段和问题第一感觉的 DP 信息不够，我就给状态里面多搞点信息；如果 DP 时间复杂度太高，而问题是状态信息太严苛，我们就把信息稍微简化一下。

还有一种可能是我们直接去看我要表示一个问题，需要用哪些未知量。把这些未知量一股脑塞进状态，就可以得到这个问题的局面，然后就只需要想怎么优化和转移了。