动态规划

这一篇完全写不完，只能把今天回顾的内容记录一遍，所以之后肯定会补充。

概念性知识（使用条件）

最优子结构

即：一个情形面前只有有限个抉择，那么要想让当前得到的结果最优，那么一定会去贪心地做出选择。

无后效性

把问题划分成阶段，那么按照逻辑顺序，当前阶段的决策不会受到之后所做的决策的影响。

可继承性

对于第 \(i-1\) 个阶段，它是第 \(i\) 个阶段的子问题，言下之意就是，前者的最优答案可以直接被后者继承，这一点在大部分实际问题中的意义表现为：在第 \(i\) 个阶段不做任何事 / 不选任何东西，直接保留 \(i-1\) 时的答案为最优解。

要素

阶段、状态、转移方程、初始条件、答案

基础问题 LIS 与 LCS

LIS 最长上升子序列

定义 \(dp[i]\) 为：以第 \(i\) 个数结尾的最长 LIS 长度

很容易写出一个 \(O(n^2)\) 的暴力转移方程 \(dp[i]=\max_j^{a[i]>a[j]}(dp[j]+1)\)，这样做在数据范围较大的情况下是会超时的。

所以我们考虑换个方式来定义 \(dp\) ，\(dp[len]\) 为：长度为 \(len\) 的 LIS 结尾数字的最小值，很显然的是在这种定义下我们只需要使用贪心的思想来更新即可，并且这样的话就出现了一个美妙的性质: \(dp\) 数组一定是单调增加的，因此可以在查找的时候二分。

枚举每一个 \(a[i]\) ，二分查找 \(dp\) 数组中最后一个小于 \(a[i]\) 的数 ，同时更新 \(dp[len]\)即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dp[N],a[N],n;
int main()
{
	int n;
	cin>>n;
	for(register int i=1;i<=n;++i)cin>>a[i];
	memset(dp,0x3f,sizeof dp);
	int ans=-1;
	for(register int i=1;i<=n;++i)
	{
		int pos=lower_bound(dp+1,dp+n+1,a[i])-dp-1;
		if(pos+1>ans)ans=pos+1;
		dp[pos+1]=min(dp[pos+1],a[i]);
	}
	cout<<ans;
	return 0;
 } 

LCS最长公共子序列问题

定义 \(dp[i][j]\) 为：序列A考虑了前 \(i\) 个，序列B考虑了前 \(j\) 个的最长LCS长度。

当 \(A[i]=B[j]\) 的时候，\(dp[i][j]=dp[i-1][j-1]+1\) 。

否则，\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])\) 。

这样做是 $O(nm) $ 的。

对于特殊情况，如 Luogu P1439，两个序列的元素实际上都相同（只是不对应相同），还有 \(O(n\log n)\) 的写法。

Code-Brute Force Ver.

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+10],b[n+10],dp[n+10][n+10];
	for(register int i=1;i<=n;++i)cin>>a[i];
	for(register int i=1;i<=n;++i)cin>>b[i];
	for(register int i=0;i<=n;++i)
		for(register int j=0;j<=n;++j)dp[i][j]=0;
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=n;++j)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
		}
	}
	cout<<dp[n][n];
	return 0;
}

Code-Better Ver.

随便给定两个题意序列 \({1,5,2,3,6,4}\) 和 $2,4,5,6,3,1 $ 其中前一个序列在后一个序列中出现的位置分别是 \(6,3,1,5,4,2\)

我们发现，从第二个序列中选出一个子序列，其位置肯定是递增的，这两者是充要关系。

那么如果我们从第三个序列（也就是抽象过后的第一个序列）中选择一段递增的数字，那么其必定是序列一二的公共子序列；进一步地，我们选择第三个序列的LIS，那么其对应的就是序列一二的 LCS。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int dp[N],a[N],b[N],idx[N];
int main()
{
	int n;
	cin>>n;
	for(register int i=1;i<=n;++i)
	{
		cin>>a[i];
		idx[a[i]]=i;
	}
	for(register int i=1;i<=n;++i)
	{
		cin>>b[i];
		a[idx[b[i]]]=i;
	}
	int ans=-1;
	memset(dp,0x3f,sizeof dp);
	for(register int i=1;i<=n;++i)
	{
		int pos=lower_bound(dp+1,dp+i,a[i])-dp-1;
		if(pos+1>ans)ans=pos+1;
		dp[pos+1]=min(dp[pos+1],a[i]);
	}
	cout<<ans;
	return 0;
}

记忆化搜索

比如用递归求解 Fibonacci 的时候，我们会经常访问同一个子问题 \(f(i)\) ，而每次都去重复地用同样的过程去求解它，这显然是无用功，所以我们用一个数组来记录每个状态对应的值，如果它没有被计算过，我们就去调用函数，并且存储最后计算出来的值；反之，直接访问数组内的值，这样就可以极大地优化效率。

下面是记忆化求 FIbonacci 的示例：

int f[N]
int get(int x)
{
	if(f[x])return f[x];
	if(x==1||x==2)return 1;
	return f[x]=get(x-1)+get(x-2);
}