线性DP

线性动态规划是动态规划中最基础的一类问题

引入部分就先省略了,重要的是多刷题找到感觉

基本步骤

• 状态表示:定义 $f[i]$ 表示前 $i$ 项的最优解(最大值、最小值、方案数等)

• 状态转移:通过前面的状态推出当前状态,写出转移方程

只要正确的完成这两步,就可以快速求解了

空间优化

我们根据状态转移方程,发现在递推的过程中,只需要前面几个量就可以往下推,所以可以节省空间,这在数据量比较大的题中会很有用

最长上升子序列(LIS)

给定一个长度为 $n$ 的数组 $a$,求最长的严格递增子序列长度.

我们令$f[i]$ 表示以 $a[i]$ 结尾的最长上升子序列长度, $f[i]$ 表示以 $a[i]$ 结尾的 LIS 长度

那么状态转移方程就为

$$f[i] = \max(f[j] + 1),\quad \text{对所有 } j < i \text{ 且 } a[j] < a[i]$$

简单吧

如果你看上去有点小蒙,别急,证明一下

值得注意的是初始化要所有 $f[i]=1$,因为每个元素自身可以组成一个长度为 $1$ 的子序列

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
int n,a[MAXN],f[MAXN];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],f[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
                f[i]=max(f[i],f[j]+1);
    cout<<*max_element(f+1,f+n+1);
}

这里有个实用的小技巧,max_element(begin,end) 可以返回指向区间中最大元素的迭代器(可以理解为指针),这里前面的* 解引用该迭代器

此时的复杂度: $O(n^2)$

贪心 + 二分优化

我们本质上是求LIS的长度而不是内容

所以可以维护一个数组 g[],表示当前长度为 $i$ 的递增子序列的最小结尾元素,这样每次找到结尾最小的元素就可以保证后面接上尽可能多的元素

思路:

• 遍历每个 $a[i]$

• 在 g 中用 lower_bound 找第一个 ≥$a[i]$ 的位置 pos :

  • 若找不到（$a[i]$ > 所有 $g[j]$）,则 $g$ 末尾加一项

  • 否则替换 $g[pos]$ 为 $a[i]$

• 最终 g.size() 就是答案.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
int n,a[MAXN],g[MAXN],len;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        int p=lower_bound(g+1,g+1+len,a[i])-g;
        g[p]=a[i];
        if(p>len)len=p;
    }
    cout<<len;
}

检验

最长公共子序列(LCS)

给定两个字符串 A 和 B,求它们的最长公共子序列的长度（不要求连续,但要顺序一致）

如果觉得抽象可以这样理解

例如：
A = "abcde"
B = "ace"
最长公共子序列是 "ace",长度为 3 ,但是"aec" "eac" "eca" "cea" 和"cae" 都不对

我们令
$A$ 长度为 $n$
$B$ 长度为 $m$
$f[i][j]$ 表示 $A$ 的前 $i$ 个字符 与 $B$ 的前 $j$ 个字符 的最长公共子序列长度

于是我们有
$$f[i][j] =
\begin{cases}
f[i-1][j-1] + 1 & \text{若 } A[i] = B[j] \\
\max(f[i-1][j],\ f[i][j-1]) & \text{否则}
\end{cases}$$

直观理解就是如果当前字符相同,就可以在原来基础上加一,否则只能继承上一个状态的最大值

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int f[N][N];
string a, b;
int main(){
    cin >> a >> b;
    int n = a.size(), m = b.size();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i-1]==b[j-1]) f[i][j] = f[i-1][j-1]+1;
            else f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
    cout << f[n][m] << endl;
}

一维优化

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int f[2][N];
string a,b;
int main(){
	cin>>a>>b;
	int n=a.size(),m=b.size();
	int t=0;
	for(int i=1;i<=n;i++){
		t^=1;
		for(int j=1;j<=m;j++){
			if(a[i-1]==b[j-1]) f[t][j]=f[t^1][j-1]+1;
			else{
				if(f[t^1][j]>f[t][j-1]) f[t][j]=f[t^1][j];
				else f[t][j]=f[t][j-1];
			}
		}
	}
	cout<<f[t][m]<<endl;
	return 0;
}

检验

做完了挑战一下这个

背包问题

01背包

设想有这样一个问题

有一个容量为 $V$ 的背包,还有 $n$ 个物体.现在忽略物体实际几何形状,我们认为只要背包的剩余容量大于等于物体体积,那就可以装进背包里.每个物体都有两个属性,即体积 $w$ 和价值 $v$ .每种物品只能选 $0$ 次或 $1$ 次如何选择物品,使得在不超过背包容量的前提下,总价值最大?

我们设第 $i$ 个物品的体积和价值分别为 $w_i,v_i$ ,对于每一个物品,我们都可以进行两个操作,那就是选与不选

如果我们令 $f[i][j]$ 表示表示前 $i$ 个物品中选出若干个放入容量为 $j$ 的背包中的最大价值
如果不选某个物品,则 $f[i][j] = f[i-1][j]$
如果容量足够且选择这个物品,则 $f[i][j] = f[i-1][j-w[i]] + v[i]$

于是状态转移方程

$$f[i][j] = \max(f[i-1][j],\ f[i-1][j-w[i]] + v[i])$$

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int n, C;
int w[MAXN], v[MAXN];
int f[MAXN][MAXN]; // f[i][j] 表示前 i 个物品中，背包容量为 j 时的最大价值

int main(){
    cin >> n >> C;//C是背包容量
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i]; // 输入物品的重量和价值

    for(int i = 1; i <= n; i++){ // 遍历所有物品
        for(int j = 0; j <= C; j++){ // 遍历所有可能的背包容量
            // 不选当前物品
            f[i][j] = f[i-1][j];
            // 如果可以放入当前物品
            if(j >= w[i]){
                f[i][j] = max(f[i][j], f[i-1][j-w[i]] + v[i]);
            }
        }
    }

    // 输出最大价值
    cout << f[n][C] << endl;
    return 0;
}

一维优化

一维数组在数据量大的情况下容易爆空间

我们发现 f[i][j] 只依行的值，即 f[i-1][j] 和 f[i-1][j - w[i]]

所以我们在处理第 i 个物品时，其实只需要用到 前一行的数据

我们引入一个一维数组 f[j] 来代替 f[i][j]，关键在于必须从大到小遍历背包容量 j（倒序）

这是因为我们要模拟 f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i])，而 f[j] 要代替 f[i][j]，我们必须保证 在更新 f[j] 时，f[j - w[i]] 仍然是上一轮（即第 i-1 件物品）留下的值，而不是当前轮刚更新过的值。

当你处理第 i 个物品时，如果你用一维数组从小到大更新（例如 for(j = w[i]; j <= C; j++)）

f[j] = max(f[j], f[j - w[i]] + v[i]);

那么 f[j - w[i]] 可能已经被本轮第 i 件物品更新过了 —— 这就相当于在同一轮里“用了两次同一个物品”，这就不是 01 背包了，而是完全背包

for(int i = 1; i <= n; i++){
    for(int j = C; j >= w[i]; j--){ // 倒序
        f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
}

这样可以确保f[j - w[i]] 是更新前的旧值（等价于 f[i-1][j - w[i]]）,f[j] 是第 i-1 件物品的最优解，现在考虑是否加入第 i 件

完全背包

与之前不同,完全背包可以对每个物品进行"多选",

我们前面说了,把01背包的第二层循环改成正序就变成了完全背包的解法,为什么是这样的呢,我们不妨先设f数组是二维的

$f[i][j]$表示表示前 $i$ 个物品中选出若干个放入容量为 $j$ 的背包中的最大价值,那么可以得出

$$f[i][j]=\max\Big(f[i-1][j],\ f[i][j-w_i]+v_i\Big)\quad(j\ge w_i)$$

它和01背包一样只依赖于上一层状态,不过我们无需倒序遍历,因为我们可以对物品多选,正序遍历可以在原来的刚才基础上继续选择最优解

一维优化

如果用滚动数组,那么可以写成这样

$$dp[j]=\max\big(dp[j],\ dp[j-w_i]+v_i\big)\quad(j\ge w_i,\ j\uparrow)$$

代码

无一维优化

#include<bits/stdc++.h>
using namespace std;
int n,V,w[10005],v[10005];
int f[1005][10005];
int main(){
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=V;j++)f[i][j]=f[i-1][j];
        for(int j=w[i];j<=V;j++)f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
    }
    cout<<f[n][V]<<endl;
}

一维优化

#include<bits/stdc++.h>
using namespace std;
int n,V,w[10005],v[10005],dp[1000005];
int main(){
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=V;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[V]<<endl;
}

多重背包

多重背包在完全背包原有的基础上发生了变异,现在你不可以无限地选择物品,每个物品的数量是有限的

我们还是从最简单的状态入手,还是每个物品选或不选,只是选择变成了选几个(变相的一种枚举)

每个物品 $i$ 有重量 $w_i$、价值 $v_i$、数量限制 $m_i$

$$f[i][j] = \text{前 } i \text{ 个物品中选若干个放入容量为 } j \text{ 的背包的最大价值}$$

那么多重背包的状态转移就是

$$f[i][j] = \max_{0 \le k \le m_i,\ k w_i \le j} \Big( f[i-1][j - k w_i] + k v_i \Big)$$

我们枚举第 $i$ 个物品取 $k$ 件,并且保证总重量不超过容量 $j$

我们发现它还是只依赖于前面的状态,于是进行一维优化

这种朴素的写法代码如下,复杂度较高

for(int i=1;i<=n;i++)
    for(int j=V;j>=0;j--)
        for(int k=1;k<=m[i] && k*w[i]<=j;k++)
            dp[j] = max(dp[j], dp[j-k*w[i]] + k*v[i]);

二进制拆分优化

我们发现数量 $m_i$ 大时,可以把它拆成若干个 01 背包物品

思路:

把第 $i$ 件、数量 $m_i$ 的物品拆成若干件 01 物品，件数为二进制块：$1,2,4,\dots, m_i-\text{sum}$。每块的 $(w,v)$ 乘以块大小。随后做 01 背包倒序转移

理解就是把每个“数量受限”的物品拆成若干个“块”（1,2,4,…,余数）,每块就是一件0-1 物品,然后用0-1 背包倒序做即可

更深层次的原理就是任意一个非负整数 $m_i$，都能表示成若干个 不重复的二进制权值 之和

为了不弄混,我们先不进行一维优化

那么

$$f[i][j]=\max_{k\in\{0,1\}}f[i-1][j],\ f[i-1][j-w_i\cdot s]+v_i\cdot s,\ \text{依次合并各块}$$

于是发现第 $i$ 层的状态还是与 $i-1$ 层状态有关,我们进行一维优化就可以得到代码

#include<bits/stdc++.h>
using namespace std;
int n,V;
vector<int>w,v,m,nw,nv;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>V;w.resize(n);v.resize(n);m.resize(n);
    for(int i=0;i<n;i++)cin>>w[i]>>v[i]>>m[i];
    for(int i=0;i<n;i++){
        int c=m[i],p=1;
        while(p<=c){nw.push_back(w[i]*p);nv.push_back(v[i]*p);c-=p;p<<=1;}
        if(c)nw.push_back(w[i]*c),nv.push_back(v[i]*c);
    }
    vector<long long>dp(V+1);
    for(int i=0;i<(int)nw.size();i++)
        for(int j=V;j>=nw[i];j--)
            dp[j]=max(dp[j],dp[j-nw[i]]+nv[i]);
    cout<<dp[V]<<'\n';
}

解释/证明

这部分确实不好理解,让我们证明一下

单调队列优化

我们发现可以把转移改写成“滑动窗口最大值”

多重背包一类物品 $(w,v,c)$ 的标准转移：

$$f'(j)=\max_{0\le t\le c,\;tw\le j}\bigl(f(j-tw)+t\,v\bigr)$$

按模 $w$ 分组，固定余数 $r\in[0,w-1]$，写

$$j=r+k\,w,\quad g_k=f(r+k\,w)$$

令 $s=k-t$（等价于 $t=k-s$），且 $t\in[0,c]\Rightarrow s\in[k-c,k]$则

$$g'_k=\max_{s\in[k-c,k]}\bigl(g_s+(k-s)\,v\bigr)
=k\,v+\max_{s\in[k-c,k]}\underbrace{\bigl(g_s-s\,v\bigr)}_{h_s}$$

对固定的 $r$，当 $k$ 从 $0,1,2,\dots$ 递增时，要求的仅是区间

$$[k-c,k]\ \text{上}\ h_s\ \text{的最大值}$$

这正是长度为 $c+1$ 的滑动窗口最大值问题

代码非常不好写,就先不详细记录了

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,V;if(!(cin>>n>>V))return 0;
    vector<int>w(n),v(n),c(n);
    for(int i=0;i<n;i++)cin>>w[i]>>v[i]>>c[i];
    const long long INF=1e18;
    vector<long long> f(V+1,-INF);f[0]=0;
    for(int i=0;i<n;i++){
        vector<long long> pre=f;
        int ww=w[i],vv=v[i],cc=c[i];
        for(int r=0;r<ww;r++){
            deque<int> q;
            for(long long k=0;;k++){
                long long j=r+k*ww; if(j>V)break;
                long long key=pre[j]-k*vv;
                while(!q.empty()){
                    long long s=q.back();
                    long long pj=r+1ll*s*ww;
                    if(pre[pj]-s*vv<=key)q.pop_back();else break;
                }
                q.push_back((int)k);
                while(!q.empty()&&q.front()<(int)(k-cc))q.pop_front();
                long long s=q.front(),pj=r+1ll*s*ww;
                f[j]=k*vv+pre[pj]-s*vv;
            }
        }
    }
    long long ans=*max_element(f.begin(),f.end());
    if(ans<-INF/2)cout<<"-inf\n";else cout<<ans<<"\n";
    return 0;
}

总结